# David P. Williamson

Affiliations:
• Cornell University, Ithaca, USA

According to our database1, David P. Williamson authored at least 103 papers between 1990 and 2022.

Collaborative distances:

## ACM Fellow

ACM Fellow 2013, "For contributions to the design and analysis of approximation algorithms.".

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2022
Tight Bounds for Online Weighted Tree Augmentation.
Algorithmica, 2022

Graph Coloring and Semidefinite Rank.
Proceedings of the Integer Programming and Combinatorial Optimization, 2022

The Two-Stripe Symmetric Circulant TSP is in P.
Proceedings of the Integer Programming and Combinatorial Optimization, 2022

2021
Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows.
CoRR, 2021

Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model.
Proceedings of the Web and Internet Economics - 17th International Conference, 2021

Recursive Random Contraction Revisited.
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

2020
Easy capacitated facility location problems, with connections to lot-sizing.
Oper. Res. Lett., 2020

Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP.
Oper. Res. Lett., 2020

Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems.
Math. Oper. Res., 2020

The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP.
CoRR, 2020

A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems.
CoRR, 2020

Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching.
CoRR, 2020

Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time.
Proceedings of the 19th IEEE International Conference on Machine Learning and Applications, 2020

2019
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem.
SIAM J. Discret. Math., 2019

Rank aggregation: New bounds for MCx.
Discret. Appl. Math., 2019

Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.
CoRR, 2019

2018
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem.
SIAM J. Optim., 2018

Online Constrained Forest and Prize-Collecting Network Design.
Algorithmica, 2018

Simple Approximation Algorithms for Balanced MAX 2SAT.
Algorithmica, 2018

2017
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds.
SIAM J. Comput., 2017

Greedy algorithms for the single-demand facility location problem.
Oper. Res. Lett., 2017

An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem.
ACM J. Exp. Algorithmics, 2017

Pricing Problems Under the Nested Logit Model with a Quality Consistency Constraint.
INFORMS J. Comput., 2017

An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem.
Algorithmica, 2017

Maximizing a Submodular Function with Viability Constraints.
Algorithmica, 2017

Prize-Collecting TSP with a Budget Constraint.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016
A Randomized O(log n)-Competitive Algorithm for the Online Connected Facility Location Problem.
Algorithmica, 2016

2015
Assortment optimization over time.
Oper. Res. Lett., 2015

On the integrality gap of the subtour LP for the 1, 2-TSP.
Math. Program., 2015

A 3/2-approximation algorithm for some minimum-cost graph problems.
Math. Program., 2015

The Online Prize-Collecting Facility Location Problem.
Electron. Notes Discret. Math., 2015

MC4, Copeland and restart probabilities.
Proceedings of the 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2015

2014
2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture.
Math. Oper. Res., 2014

Popular ranking.
Discret. Appl. Math., 2014

On Some Recent Approximation Algorithms for MAX SAT.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

The Online Connected Facility Location Problem.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

2013
An Experimental Evaluation of Incremental and Hierarchical <i>k</i>-Median Algorithms.
ACM J. Exp. Algorithmics, 2013

Offline and online facility leasing.
Discret. Optim., 2013

On Some Recent MAX SAT Approximation Algorithms.
CoRR, 2013

2012
A proof of the Boyd-Carr conjecture.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

A Dual-Fitting $\frac{3}{2}$ -Approximation Algorithm for Some Minimum-Cost Graph Problems.
Proceedings of the Algorithms - ESA 2012, 2012

2011
A note on the generalized min-sum set cover problem.
Oper. Res. Lett., 2011

On the Integrality Gap of the Subtour LP for the 1,2-TSP
CoRR, 2011

An <i>O</i>(log<i>n</i>)-Competitive Algorithm for Online Constrained Forest Problems.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

The Design of Approximation Algorithms.
Cambridge University Press, ISBN: 978-0-521-19527-0, 2011

2010
A General Approach for Incremental Approximation and Hierarchical Clustering.
SIAM J. Comput., 2010

2009
Approximating the smallest <i>k</i>-edge connected spanning subgraph by LP-rounding.
Networks, 2009

A simple GAP-canceling algorithm for the generalized maximum flow problem.
Math. Program., 2009

Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems.
Math. Oper. Res., 2009

Stackelberg thresholds in network routing games or the value of altruism.
Games Econ. Behav., 2009

2008
A Faster, Better Approximation Algorithm for the Minimum Latency Problem.
SIAM J. Comput., 2008

Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements.
Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

2007
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy.
Oper. Res. Lett., 2007

Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems.
Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

Deterministic pivoting algorithms for constrained ranking and clustering problems.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Approximation algorithms for prize collecting forest problems with submodular penalty functions.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems.
Theor. Comput. Sci., 2006

Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems.
J. Comput. Syst. Sci., 2006

Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

2005
Improved approximation algorithms for capacitated facility location problems.
Math. Program., 2005

2004
Approximate <i>k</i>-MSTs and <i>k</i>-Steiner trees via the primal-dual method and Lagrangean relaxation.
Math. Program., 2004

Approximation algorithms for M<sub>AX</sub>-3-C<sub>UT</sub> and other problems via complex semidefinite programming.
J. Comput. Syst. Sci., 2004

2003
Searching the workplace web.
Proceedings of the Twelfth International World Wide Web Conference, 2003

Faster approximation algorithms for the minimum latency problem.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

2002
The primal-dual method for approximation algorithms.
Math. Program., 2002

A primal-dual schema based approximation algorithm for the element connectivity problem.
J. Algorithms, 2002

Improved Approximation Algorithms for MAX SAT.
J. Algorithms, 2002

Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems.
Algorithmica, 2002

2001
J. ACM, 2001

Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation.
Proceedings of the Integer Programming and Combinatorial Optimization, 2001

An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler.
SIAM J. Discret. Math., 2000

SIAM J. Comput., 2000

The Approximability of Constraint Satisfaction Problems.
SIAM J. Comput., 2000

Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout.
SIAM J. Comput., 2000

A 1.47-approximation algorithm for a preemptive single-machine scheduling problem.
Oper. Res. Lett., 2000

1998
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs.
Oper. Res. Lett., 1998

An efficient approximation algorithm for the survivable network design problem.
Math. Program., 1998

Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs.
Comb., 1998

1997
Short Shop Schedules.
Oper. Res., 1997

An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems.
Algorithmica, 1997

Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1997

A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996
On the Number of Small Cuts in a Graph.
Inf. Process. Lett., 1996

Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances.
INFORMS J. Comput., 1996

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction
Electron. Colloquium Comput. Complex., 1996

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Primal-Dual Approximation Algorithms for Feedback Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996

Gadgets, Approximation, and Linear Programming (extended abstract).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
Scheduling Parallel Machines On-Line.
SIAM J. Comput., 1995

A General Approximation Technique for Constrained Forest Problems.
SIAM J. Comput., 1995

Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.
J. ACM, 1995

A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems.
Comb., 1995

1994
New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem.
SIAM J. Discret. Math., 1994

Approximating minimum-cost graph problems with spanning tree edges.
Oper. Res. Lett., 1994

.879-approximation algorithms for MAX CUT and MAX 2SAT.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Improved Approximation Algorithms for Network Design Problems.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
A note on the prize collecting traveling salesman problem.
Math. Program., 1993

A new \frac34-approximation algorithm for MAX SAT.
Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

1992
Analysis of the Held-Karp lower bound for the asymmetric TSP.
Oper. Res. Lett., 1992

1991
Permutation vs. non-permutation flow shop schedules.
Oper. Res. Lett., 1991

1990
Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application.
Inf. Process. Lett., 1990