David P. Williamson

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

Collaborative distances:

Awards

ACM Fellow

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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

Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time.
CoRR, 2020

Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing.
CoRR, 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

Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP.
CoRR, 2019

Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.
CoRR, 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 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 k-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 O(logn)-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 k-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

An adaptive algorithm for selecting profitable keywords for search-based advertising services.
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 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

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
Adversarial queuing theory.
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

Gadgets, Approximation, and Linear Programming.
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.
Combinatorica, 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
Electronic Colloquium on Computational Complexity (ECCC), 1996

Adversarial Queueing Theory.
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.
Combinatorica, 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


  Loading...