A Lower Bound on the Max Entropy Algorithm for TSP
To appear in IPCO 2024
Preprint
Max Cut and Semidefinite Rank
Operations Research Letters 53, Article 107067, 2024.
DOI
Erratum to 'Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems'
Mathematics of Operations Research 48:2304-2307, 2023
DOI
An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut
ACM Journal of Experimental Algorithmics 28. Article 2.1, pages 1-18, 2023.
Code
DOI
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
Algorithmica 85:3680-3718, 2023.
DOI
Fluid Approximations for Revenue Management under High-Variance Demand: Good and Bad Formulations
Management Science 69:3759-4361, 2023.
Preprint
DOI
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
The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP
Mathematics of Operations Research 48:393–418, 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
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
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
Mathematics of Operations Research 47:1-28, 2022.
Preprint
DOI
Tight Bounds for Online Weighted Tree Augmentation
Algorithmica 84:304-324, 2022.
Preprint
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
Recursive Random Contraction Revisited
In the Proceedings of the 2021 SIAM Symposium on Simplicity in Algorithms, pages 68-73, 2021.
Preprint
DOI
Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time
In the Proceedings of the 19th IEEE International Conference on Machine Learning and Applications, pages 19-24, 2020.
Preprint
DOI
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
Mathematics of Operations Research 45:576-590, 2020.
DOI
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
Operations Research Letters 48:245-248, 2020.
Preprint
DOI
Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing
Operations Research Letters 48:109-114, 2020.
Preprint
DOI
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
SIAM Journal on Discrete Mathematics 33:2452-2478, 2019
Preprint
DOI
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
Online Constrained Forest and Prize-Collecting Network Design
Algorithmica 80:3335-3364, 2018.
DOI
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
SIAM Journal on Optimization 28:2073-2096, 2018.
Preprint
DOI
Simple Approximation Algorithms for Balanced MAX 2SAT
Algorithmica 80:995-1012, 2018.
DOI
Greedy Algorithms for the Single-Demand Facility Location Problem
Operations Research Letters 45:452-455, 2017.
DOI
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
An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
ACM Journal of Experimental Algorithmics 22, Article 1.6, 2017
DOI
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem
Algorithmica 78:1109-1130, 2017.
DOI
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
SIAM Journal on Computing 46:1029-1061, 2017
DOI
Pricing Problems Under the Nested Logit Model with a Quality Consistency Constraint
INFORMS Journal on Computing 29:54-76, 2017
DOI
Maximizing a submodular function with viability constraints
Algorithmica 77:152-172, 2017.
DOI
A Randomized O(log n)-Competitive Algorithm for the Online Connected Facility Location Problem
Algorithmica 76:1139-1157, 2016.
DOI
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
Assortment optimization over time.
Operations Research Letters 43:608-611, 2015
DOI
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
On the Integrality Gap of the Subtour LP for the 1,2-TSP
Mathematical Programming 150:131-151, 2015.
DOI
A 3/2-approximation algorithm for some minimum-cost graph problems
Mathematical Programming 150:19-34, 2015.
DOI
The Online Prize-Collecting Facility Location Problem
Electronic Notes in Discrete Mathematics 50:151–156, 2015
2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
Mathematics of Operations Research 39:403-417, 2014.
DOI
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
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
Offline and Online Facility Leasing
Discrete Optimization 10:361–370, 2013.
DOI
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
A note on the generalized min-sum set cover problem
Operations Research Letters 39:433-436, 2011.
Preprint
DOI
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
A general approach for incremental approximation and hierarchical clustering.
SIAM Journal on Computing 39:3633-3669, 2010.
DOI
Stackelberg thresholds in network routing games or the value of altruism.
Games and Economic Behavior 67:174-190, 2009.
DOI
Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems.
Mathematics of Operations Research 34:594-620, 2009.
DOI
Approximating the smallest $k$-edge connected spanning subgraph by LP-rounding.
Networks 53:345-357, 2009.
DOI
A Simple GAP-canceling algorithm for the Generalized Maximum Flow Problem.
Mathematical Programming 118:47-74, 2009.
DOI
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
A faster, better approximation algorithm for the minimum latency problem.
SIAM Journal on Computing 37:1472-1498, 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
A Simpler and Better Derandomization of an Approximation Algorithm for Single Source Rent-or-Buy.
Operations Research Letters 35:707-712, 2007.
DOI
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
On the relationship between combinatorial and LP-based lower bounds to NP-hard scheduling problems.
Theoretical Computer Science 361:241-256, 2006.
DOI
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems.
Journal of Computer and System Sciences 72:838-867, 2006.
DOI
An adaptive algorithm for selecting profitable keywords for search-based advertising services.
Proceedings of the 7th ACM Conference on Electronic Commerce, pages 260-269, 2006.
DOI
Improved approximation algorithms for capacitated facility location problems
Mathematical Programming 102:207-222, 2005.
DOI
Approximate $k$-MSTs and $k$-Steiner trees via the primal-dual method and Lagrangean relaxation.
Mathematical Programming 100:411-421, 2004.
DOI
Approximation Algorithms for MAX 3-CUT and Other Problems via Complex Semidefinite Programming.
Journal of Computer and System Sciences 68:442-470, 2004.
DOI
Lecture Notes on Advanced Algorithms, Spring 2003.
IBM Research Report RJ 10296.
PDF
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
Erratum: An Approximation Algorithm for Minimum-Cost Vertex Connectivity Problems.
Algorithmica 34:98-107, 2002.
DOI
A primal-dual schema based approximation algorithm for the element connectivity problem.
Journal of Algorithms 45:1-15, 2002.
DOI
The Primal-Dual Method for Approximation Algorithms.
Mathematical Programming 91:447-478, 2002.
DOI
Improved approximation algorithms for MAX SAT.
Journal of Algorithms 42:173-202, 2002.
DOI
The Approximability of Constraint Satisfaction Problems.
SIAM Journal on Computing 30:1863-1920, 2001.
DOI
Adversarial Queueing Theory.
Journal of the ACM 48:13-38, 2001.
DOI
Gadgets, Approximation, and Linear Programming.
SIAM Journal on Computing 29:2074-2097, 2000.
DOI
Two-dimensional Gantt charts and a scheduling algorithm of Lawler.
SIAM Journal on Discrete Mathematics 13:281-294, 2000.
DOI
Node Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout.
SIAM Journal on Computing 29:1321-1333, 2000.
DOI
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem.
Operations Research Letters 26:149-154, 2000.
DOI
Lecture Notes in Approximation Algorithms, Fall 1998.
IBM Research Report RC 21409, 1999.
PDF
Lecture Notes in Approximation Algorithms, Spring 1998.
IBM Research Report RC 21273, 1998.
PDF
An Efficient Approximation Algorithm for the Survivable Network Design Problem.
Mathematical Programming 82:13-40, 1998.
DOI
A Primal-Dual Interpretation of Two 2-Approximation Algorithms for the Feedback Vertex Set Problem in Undirected Graphs.
Operations Research Letters , 22:111-118, 1998.
DOI
Primal-dual approximation algorithms for feedback problems in planar graphs.
Combinatorica 18:37-59, 1998.
DOI
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
Short shop schedules.
Operations Research 45:288-294, 1997.
DOI
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
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances.
INFORMS Journal on Computing 8:29-40, 1996.
DOI
Scheduling parallel machines on-line.
SIAM Journal on Computing 24:1313-1331, 1995.
DOI
A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems.
Combinatorica 15:435-454, 1995.
DOI
Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming
Journal of the ACM 42:1115–1145, 1995.
DOI
A general approximation technique for constrained forest problems.
SIAM Journal on Computing 24:296–317, 1995.
DOI
New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem.
SIAM Journal on Discrete Mathematics 7:656-666, 1994.
DOI
Approximating minimum-cost graph problems with spanning tree edges.
Operations Research Letters 16:183-189, 1994.
DOI
Improved approximation algorithms for network design problems.
Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms , pages 223-232, 1994.
DOI
On the design of approximation algorithms for a class of graph problems.
Ph.D. thesis, MIT, Cambridge, MA, USA, September 1993.
PDF
A note on the prize-collecting traveling salesman problem.
Mathematical Programming 59:413-420, 1993.
DOI
Analysis of the Held-Karp lower bound for the asymmetric TSP.
Operations Research Letters 12:83-88, 1992.
DOI
Permutation vs. non-permutation flow shop schedules.
Operations Research Letters 10:281-284, 1991.
DOI
Analyzing the Held-Karp TSP bound: A monotonicity property with application.
Information Processing Letters 35:281-285, 1990.
DOI
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