Publications

2024


Max Cut and Semidefinite Rank
Operations Research Letters 53, Article 107067, 2024.
DOI

2023


A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
In Albert Del Pia and Volker Kaibel, editors, Lecture Notes in Computer Science volume 13904, Integer Programming and Combinatorial Optimization (IPCO 2023), pages 217-230, 2023.
Preprint DOI


GILP: An Interactive Tool for Visualizing the Simplex Algorithm
In the SIGCSE 2023: Proceedings of the 54th ACM Technical Symposium on Computer Science Education, pages 108-114, 2023.
DOI


Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs
In the Proceedings of the 2023 Symposium on Simplicity in Algorithms (SOSA), pages 56–68, 2023.
DOI


A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Systems
In the Proceedings of the 15th Innovations in Theoretical Computer Science Conference (ITCS 2023), 69:1–69:22, 2023.
DOI

2022


An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut
In Christian Schulz and Bora Ucar, editors, Leibniz International Proceedings in Informations 233, 20th International Symposium on Experimental Algorithms (SEA 2022), 19:1-19:14, 2022.
PDF Code DOI


The Two-Stripe Symmetric Circulant TSP is in P
In Karen Aardal and Laura Sanita, editors, Lecture Notes in Computer Science volume 13265, Integer Programming and Combinatorial Optimization (IPCO 2022), 319-332, 2022.
Preprint DOI


Graph Coloring and Semidefinite Rank
In Karen Aardal and Laura Sanita, editors, Lecture Notes in Computer Science volume 13265, Integer Programming and Combinatorial Optimization (IPCO 2022), 387-401, 2022.
Preprint Code DOI


Improved Analysis of RANKING for Online Vertex-Weighted Matching in the Random Order Model
In the Proceedings of the 17th International Conference on Web and Internet Economics (WINE 2021), pages 207-225, 2022.
Preprint DOI

2021


Recursive Random Contraction Revisited
In the Proceedings of the 2021 SIAM Symposium on Simplicity in Algorithms, pages 68-73, 2021.
Preprint DOI

2020

2019


Network Flow Algorithms
Cambridge University Press, New York, NY, USA, 2019.
PDF


Tight Bounds for Online Weighted Tree Augmentation
In Christel Baier, Ioannis Chatzigiannakis, Paola Flochinni, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , 88:1-88:14, 2019.
Preprint DOI


Rank Aggregation: New Bounds for MCx
Discrete Applied Mathematics 262:28-36, 2019.
DOI

2018

2017


Prize-Collecting TSP with a Budget Constraint
In Kirk Pruhs and Christian Soler, editors, Leibnitz International Proceedings in Informatics Number 87, 25th Annual European Symposium on Algorithms (ESA 2017), pages 62:1-62:14, 2017.
DOI

2016


An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
In Andrew V. Goldberg and Alexander S. Kulikov, editors, Lecture Notes in Computer Science Number 9685, Experimental Algorithms, 15th International Symposium, SEA 2016 pages 246-261, 2016
DOI


Simple Approximation Algorithms for Balanced MAX 2SAT
In Evangelos Kranakis, Gonzalo Navarro, and Edgar Chávez, editors, Lecture Notes in Computer Science Number 9644, LATIN 2016: Theoretical Informatics, pages 659-671, 2016.
DOI

2015


An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem
In Nikhil Bansal and Irene Finocchi, editors, Lecture Notes in Computer Science Number 9294, Algorithms – ESA 2015, pages 570-581, 2015.
Preprint DOI


The Online Prize-Collecting Facility Location Problem
Electronic Notes in Discrete Mathematics 50:151–156, 2015

2014


The Online Connected Facility Location Problem
In Alberto Pardo and Alfredo Viola, editors, Lecture Notes in Computer Science Number 8392, LATIN 2014: Theoretical Informatics , pages 574-585, 2014.
DOI


On Some Recent Approximation Algorithms for MAX SAT
In Alberto Pardo and Alfredo Viola, editors, Lecture Notes in Computer Science Number 8392, LATIN 2014: Theoretical Informatics , pages 589-609, 2014.
Preprint DOI


Popular ranking
Discrete Applied Mathematics 165:312-316, 2014.
DOI

2013


An Experimental Evaluation of Incremental and Hierarchical $k$-Median Algorithms
Journal of Experimental Algorithmics 18, Article 3.2. Special issue for the 2011 Symposium on Experimental Algorithms.
DOI


Maximizing a Submodular Function with Viability Constraints
In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Lecture Notes in Computer Science , vol. 8125, Algorithms – ESA 2013 , pages 409-420, 2013.
DOI

2012


A dual-fitting 3/2-approximation algorithm for some minimum-cost graph problems
In Leah Epstein and Paolo Ferragina, editors, Lecture Notes in Computer Science, vol. 7501, Algorithms – ESA 2012 , pages 373–382, 2012.
DOI


On the integrality gap of the Subtour LP for the 1,2-TSP
In David Fernández-Baca, editor, Lecture Notes in Computer Science, vol. 7256, LATIN 2012: Theoretical Informatics, pages 606-617, 2012.
Preprint DOI


A proof of the Boyd-Carr conjecture
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1477-1486, 2012.
Preprint DOI

2011


An O(log n)-competitive algorithm for online constrained forest problems
In Luca Aceto, Monika Henzinger, and Jiří Sgall, editors, Lecture Notes in Computer Science, vol. 6755, Automata, Languages, and Programming, pages 37-48, 2011.
DOI


Popular ranking
In the Proceedings of the 10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2011).
PDF


An experimental evaluation of incremental and hierarchical $k$-median algorithms
In Panos M. Pardalos and Steffen Rebennack, editors, Lecture Notes in Computer Science, vol. 6630, Experimental Algorithms, pages 169–180, 2011.
DOI


The Design of Approximation Algorithms
Cambridge University Press, New York, NY, USA, 2011.
PDF

2010

2009

2008


Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements.
In E. Bampis and M. Skutella, editors, Lecture Notes in Computer Science, vol. 5426, Approximation and Online Algorithms, pages 174-187, 2008.
DOI


Offline and Online Facility Leasing.
In A. Lodi, A. Paconesi, and G. Rinaldi, editors, Lecture Notes in Computer Science, vol. 5035, Integer Programming and Combinatorial Optimization, pages 303-315, 2008.
DOI

2007


Lecture Notes on Network Flow, Spring 2004.
Cornell School of Operations Research and Information Engineering Technical Report 1460.
PDF


Approximation algorithms for prize collecting forest problems with submodular penalty functions.
Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms, pages 1275-1284, 2007.
DOI

2006

2005


Improved approximation algorithms for capacitated facility location problems
Mathematical Programming 102:207-222, 2005.
DOI

2004

2003


Searching the workplace web.
Proceedings of the 12th International World Wide Web Conference, pages 366-375, 2003.
DOI


Faster approximation algorithms for the minimum latency problem
Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms, pages 88-96, 2003.
DOI

2002

2001

2000

1999

1998

1997


Approximation Algorithms.
Proceedings of the National Academy of Sciences 94:12734–12735, 1997.
PDF


An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems.
Algorithmica 18:21-43, 1997. See also Erratum in Algorithmica 34:98-107.
DOI

1996


On the Number of Small Cuts in a Graph.
Information Processing Letters 59:41-44, 1996.
DOI


The primal-dual method for approximation algorithms and its application to network design problems.
In Approximation Algorithms for NP-hard Problems , Dorit S. Hochbaum, editor. PWS Publishing Company, Boston, MA, USA, 1996.
PDF

1995


Scheduling parallel machines on-line.
SIAM Journal on Computing 24:1313-1331, 1995.
DOI

1994


Improved approximation algorithms for network design problems.
Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms , pages 223-232, 1994.
DOI

1993

1992

1991

1990


Analysis of the Held-Karp heuristic for the traveling salesman problem.
Master’s thesis, MIT, Cambridge, MA, USA, June 1990. Also appears as MIT LCS Technical Report TR-479.
PDF