| Publication | Date of Publication | Type |
|---|
The two-stripe symmetric circulant TSP is in P
Mathematical Programming. Series A. Series B | 2026-01-16 | Paper |
A \(\frac{4}{3} \)-approximation algorithm for half-integral cycle cut instances of the TSP
Mathematical Programming. Series A. Series B | 2025-03-05 | Paper |
| A lower bound for the max entropy algorithm for TSP | 2025-02-07 | Paper |
| A combinatorial cut-toggling algorithm for solving Laplacian linear systems | 2024-09-25 | Paper |
Graph coloring and semidefinite rank
Mathematical Programming. Series A. Series B | 2024-08-20 | Paper |
An experimental evaluation of semidefinite programming and spectral algorithms for max cut
ACM Journal of Experimental Algorithmics | 2024-07-26 | Paper |
Max cut and semidefinite rank
Operations Research Letters | 2024-07-01 | Paper |
| Recursive random contraction revisited | 2024-05-14 | Paper |
| Revisiting Garg's 2-approximation algorithm for the \(k\)-MST problem in graphs | 2024-05-14 | Paper |
Erratum to “Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems”
Mathematics of Operations Research | 2024-03-01 | Paper |
The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP
Mathematics of Operations Research | 2024-02-23 | Paper |
A combinatorial cut-toggling algorithm for solving Laplacian linear systems
Algorithmica | 2023-12-13 | Paper |
A combinatorial cut-toggling algorithm for solving Laplacian linear systems
Algorithmica | 2023-12-13 | Paper |
A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
Integer Programming and Combinatorial Optimization | 2023-11-09 | Paper |
| A Lower Bound for the Max Entropy Algorithm for TSP | 2023-11-03 | Paper |
The two-stripe symmetric circulant TSP is in P
(available as arXiv preprint) | 2022-08-16 | Paper |
Graph coloring and semidefinite rank
(available as arXiv preprint) | 2022-08-16 | Paper |
Tight bounds for online weighted tree augmentation
(available as arXiv preprint) | 2022-07-21 | Paper |
Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model
(available as arXiv preprint) | 2022-07-06 | Paper |
Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps
Mathematics of Operations Research | 2022-05-17 | Paper |
Tight bounds for online weighted tree augmentation
Algorithmica | 2022-03-25 | Paper |
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
Mathematics of Operations Research | 2020-09-01 | Paper |
| Prize-collecting TSP with a budget constraint | 2020-05-27 | Paper |
Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP
Operations Research Letters | 2020-05-26 | Paper |
Easy capacitated facility location problems, with connections to lot-sizing
Operations Research Letters | 2020-04-07 | Paper |
Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing
(available as arXiv preprint) | 2020-01-08 | Paper |
Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
SIAM Journal on Discrete Mathematics | 2019-12-18 | Paper |
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
(available as arXiv preprint) | 2019-07-26 | Paper |
| Network flow algorithms | 2019-05-21 | Paper |
A proof of the Boyd-Carr conjecture
(available as arXiv preprint) | 2019-05-10 | Paper |
| A proof of the Boyd-Carr conjecture | 2019-05-10 | Paper |
Greedy algorithms for the single-demand facility location problem
Operations Research Letters | 2019-02-22 | Paper |
Online constrained forest and prize-collecting network design
Algorithmica | 2019-01-11 | Paper |
Primal-dual approximation algorithms for feedback problems in planar graphs
Integer Programming and Combinatorial Optimization | 2019-01-11 | Paper |
Rank aggregation: new bounds for MCx
Discrete Applied Mathematics | 2018-12-10 | Paper |
Offline and online facility leasing
Discrete Optimization | 2018-10-18 | Paper |
Assortment optimization over time
Operations Research Letters | 2018-09-28 | Paper |
An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
ACM Journal of Experimental Algorithmics | 2018-08-06 | Paper |
The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
SIAM Journal on Optimization | 2018-08-03 | Paper |
Simple approximation algorithms for balanced MAX~2SAT
Algorithmica | 2018-04-11 | Paper |
An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem
Algorithmica | 2017-10-10 | Paper |
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
SIAM Journal on Computing | 2017-06-28 | Paper |
An experimental evaluation of incremental and hierarchical \(k\)-median algorithms
ACM Journal of Experimental Algorithmics | 2017-06-16 | Paper |
Pricing problems under the nested logit model with a quality consistency constraint
INFORMS Journal on Computing | 2017-06-02 | Paper |
Maximizing a submodular function with viability constraints
Algorithmica | 2017-03-06 | Paper |
A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
Algorithmica | 2016-12-21 | Paper |
| The online prize-collecting facility location problem | 2016-10-17 | Paper |
.878-approximation algorithms for MAX CUT and MAX 2SAT
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Simple Approximation Algorithms for Balanced MAX 2SAT
LATIN 2016: Theoretical Informatics | 2016-05-03 | Paper |
An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem
Lecture Notes in Computer Science | 2015-11-19 | Paper |
Adversarial queuing theory
Journal of the ACM | 2015-09-20 | Paper |
A primal-dual approximation algorithm for generalized Steiner network problems
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
On the integrality gap of the subtour LP for the 1,2-TSP
Mathematical Programming. Series A. Series B | 2015-04-16 | Paper |
A 3/2-approximation algorithm for some minimum-cost graph problems
Mathematical Programming. Series A. Series B | 2015-04-16 | Paper |
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
| Approximation algorithms for prize collecting forest problems with submodular penalty functions | 2014-12-18 | Paper |
| Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding | 2014-10-13 | Paper |
2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
Mathematics of Operations Research | 2014-07-11 | Paper |
Popular ranking
Discrete Applied Mathematics | 2014-05-05 | Paper |
On Some Recent Approximation Algorithms for MAX SAT
LATIN 2014: Theoretical Informatics | 2014-03-31 | Paper |
The online connected facility location problem
LATIN 2014: Theoretical Informatics | 2014-03-31 | Paper |
Maximizing a submodular function with viability constraints
Lecture Notes in Computer Science | 2013-09-17 | Paper |
A dual-fitting \(\frac{3}{2}\)-approximation algorithm for some minimum-cost graph problems
Algorithms – ESA 2012 | 2012-09-25 | Paper |
On the integrality gap of the subtour LP for the \(1,2\)-TSP
LATIN 2012: Theoretical Informatics | 2012-06-29 | Paper |
A note on the generalized min-sum set cover problem
Operations Research Letters | 2012-04-05 | Paper |
An \(O(\log n)\)-competitive algorithm for online constrained forest problems
Automata, Languages and Programming | 2011-07-06 | Paper |
| The design of approximation algorithms | 2011-07-01 | Paper |
Deterministic pivoting algorithms for constrained ranking and clustering problems
Mathematics of Operations Research | 2011-04-27 | Paper |
A general approach for incremental approximation and hierarchical clustering
SIAM Journal on Computing | 2011-04-04 | Paper |
Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
Networks | 2010-11-24 | Paper |
A general approach for incremental approximation and hierarchical clustering
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
A simple GAP-canceling algorithm for the generalized maximum flow problem
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Stackelberg thresholds in network routing games or the value of altruism
Games and Economic Behavior | 2009-08-27 | Paper |
A simple GAP-canceling algorithm for the generalized maximum flow problem
Mathematical Programming. Series A. Series B | 2009-05-04 | Paper |
Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
Approximation and Online Algorithms | 2009-02-12 | Paper |
A Faster, Better Approximation Algorithm for the Minimum Latency Problem
SIAM Journal on Computing | 2008-10-28 | Paper |
Offline and Online Facility Leasing
Integer Programming and Combinatorial Optimization | 2008-06-10 | Paper |
Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
Approximation and Online Algorithms | 2008-02-20 | Paper |
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
Operations Research Letters | 2008-01-21 | Paper |
On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems
Theoretical Computer Science | 2006-09-14 | Paper |
Improved approximation algorithms for capacitated facility location problems
Mathematical Programming. Series A. Series B | 2005-04-19 | Paper |
| scientific article; zbMATH DE number 2119765 (Why is no real title available?) | 2004-11-29 | Paper |
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
Journal of Computer and System Sciences | 2004-11-22 | Paper |
Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
Mathematical Programming. Series A. Series B | 2004-10-05 | Paper |
| scientific article; zbMATH DE number 2079325 (Why is no real title available?) | 2004-07-28 | Paper |
On the number of small cut in a graph
Information Processing Letters | 2003-06-24 | Paper |
Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
Algorithmica | 2002-12-01 | Paper |
The primal-dual method for approximation algorithms
Mathematical Programming. Series A. Series B | 2002-12-01 | Paper |
Improved approximation algorithms for MAX SAT
Journal of Algorithms | 2002-08-14 | Paper |
| scientific article; zbMATH DE number 1757947 (Why is no real title available?) | 2002-06-20 | Paper |
| scientific article; zbMATH DE number 1741105 (Why is no real title available?) | 2002-05-15 | Paper |
The approximability of constraint satisfaction problems
SIAM Journal on Computing | 2001-03-19 | Paper |
| scientific article; zbMATH DE number 1342123 (Why is no real title available?) | 2001-03-04 | Paper |
| scientific article; zbMATH DE number 1559517 (Why is no real title available?) | 2001-02-28 | Paper |
| scientific article; zbMATH DE number 1445292 (Why is no real title available?) | 2001-01-18 | Paper |
Gadgets, Approximation, and Linear Programming
SIAM Journal on Computing | 2000-10-18 | Paper |
| scientific article; zbMATH DE number 1305426 (Why is no real title available?) | 2000-09-26 | Paper |
A 1. 47-approximation for a preemptive single-machine scheduling problem
Operations Research Letters | 2000-09-04 | Paper |
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
SIAM Journal on Discrete Mathematics | 2000-07-20 | Paper |
| scientific article; zbMATH DE number 1256755 (Why is no real title available?) | 2000-04-04 | Paper |
Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout
SIAM Journal on Computing | 2000-03-19 | Paper |
Primal-dual approximation algorithms for feedback problems in planar graphs
Combinatorica | 1999-10-31 | Paper |
| scientific article; zbMATH DE number 1263260 (Why is no real title available?) | 1999-10-28 | Paper |
An efficient approximation algorithm for the survivable network design problem
Mathematical Programming. Series A. Series B | 1999-10-18 | Paper |
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
Operations Research Letters | 1999-09-23 | Paper |
| scientific article; zbMATH DE number 1263278 (Why is no real title available?) | 1999-03-16 | Paper |
| scientific article; zbMATH DE number 1256778 (Why is no real title available?) | 1999-03-01 | Paper |
Short Shop Schedules
Operations Research | 1998-07-06 | Paper |
Approximation algorithms
Proceedings of the National Academy of Sciences | 1998-04-03 | Paper |
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Journal of the ACM | 1998-01-28 | Paper |
An approximation algorithm for minimum-cost vertex-connectivity problems
Algorithmica | 1997-10-09 | Paper |
| scientific article; zbMATH DE number 1003267 (Why is no real title available?) | 1997-08-04 | Paper |
| scientific article; zbMATH DE number 1003253 (Why is no real title available?) | 1997-04-23 | Paper |
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances
INFORMS Journal on Computing | 1996-10-28 | Paper |
Scheduling Parallel Machines On-Line
SIAM Journal on Computing | 1996-09-15 | Paper |
| scientific article; zbMATH DE number 910889 (Why is no real title available?) | 1996-08-22 | Paper |
A General Approximation Technique for Constrained Forest Problems
SIAM Journal on Computing | 1996-03-18 | Paper |
A primal-dual approximation algorithm for generalized Steiner network problems
Combinatorica | 1995-10-17 | Paper |
Approximating minimum-cost graph problems with spanning tree edges
Operations Research Letters | 1995-07-06 | Paper |
| scientific article; zbMATH DE number 742977 (Why is no real title available?) | 1995-04-11 | Paper |
New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
SIAM Journal on Discrete Mathematics | 1994-12-20 | Paper |
A note on the prize collecting traveling salesman problem
Mathematical Programming. Series A. Series B | 1994-08-16 | Paper |
Analysis of the Held-Karp lower bound for the asymmetric TSP
Operations Research Letters | 1993-01-16 | Paper |
| scientific article; zbMATH DE number 65706 (Why is no real title available?) | 1992-09-27 | Paper |
Permutation vs. non-permutation flow shop schedules
Operations Research Letters | 1992-06-27 | Paper |
Analyzing the Held-Karp TSP bound: A monotonicity property with application
Information Processing Letters | 1990-01-01 | Paper |
