# David P. Williamson

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

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

2019
Rank aggregation: New bounds for MCx.
Discrete Applied Mathematics, 2019

Tight Bounds for Online Weighted Tree Augmentation.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem.
SIAM Journal on Optimization, 2018

Online Constrained Forest and Prize-Collecting Network Design.
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

Pricing Problems Under the Nested Logit Model with a Quality Consistency Constraint.
INFORMS Journal on Computing, 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

An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem.
Proceedings of the Experimental Algorithms - 15th International Symposium, 2016

Simple Approximation Algorithms for Balanced MAX 2SAT.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

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

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

The Online Prize-Collecting Facility Location Problem.
Electronic Notes in Discrete Mathematics, 2015

An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem.
Proceedings of the Algorithms - ESA 2015, 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

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
Maximizing a Submodular Function with Viability Constraints.
Proceedings of the Algorithms - ESA 2013, 2013

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

On the Integrality Gap of the Subtour LP for the 1, 2-TSP.
Proceedings of the LATIN 2012: Theoretical Informatics, 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

An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms.
Proceedings of the Experimental Algorithms - 10th International Symposium, 2011

An O(logn)-Competitive Algorithm for Online Constrained Forest Problems.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Popular Ranking.
Proceedings of the 10th Cologne-Twente Workshop on graphs and combinatorial optimization. Extended Abstracts, 2011

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

2009
Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems.
Math. Oper. Res., 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

Offline and Online Facility Leasing.
Proceedings of the Integer Programming and Combinatorial Optimization, 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

Stackelberg thresholds in network routing games or the value of altruism.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 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

A simple GAP-canceling algorithm for the generalized maximum flow problem.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

A general approach for incremental approximation and hierarchical clustering.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

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

2005
Approximating the smallest k-edge connected spanning subgraph by LP-rounding.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

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

Approximation algorithms for MAX-3-CUT 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

Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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
SIAM J. Comput., 2000

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

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

Improved approximation algorithms for MAX SAT.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Improved Approximation Algorithms for Capacitated Facility Location Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 1999

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

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

1997
Short Shop Schedules.
Operations Research, 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

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction
Electronic Colloquium on Computational Complexity (ECCC), 1996

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

Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout.
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
Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.
J. ACM, 1995

1994
New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem.
SIAM J. Discrete 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

Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 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 primal-dual approximation algorithm for generalized Steiner network problems.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

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

An efficient approximation algorithm for the survivable network design problem.
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

A General Approximation Technique for Constrained Forest Problems.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

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

Scheduling Parallel Machines On-Line
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Scheduling Parallel Machines On-line.
Proceedings of the On-Line Algorithms, 1991

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