David P. Williamson
Orcid: 0000-0002-2884-0058Affiliations:
- Cornell University, Ithaca, USA
According to our database1,
David P. Williamson
authored at least 113 papers
between 1990 and 2023.
Collaborative distances:
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 Dataset OtherLinks
Online presence:
-
on zbmath.org
-
on orcid.org
-
on id.loc.gov
-
on d-nb.info
-
on dl.acm.org
On csauthors.net:
Bibliography
2023
An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut.
ACM J. Exp. Algorithmics, December, 2023
Algorithmica, December, 2023
Manag. Sci., July, 2023
Math. Program., February, 2023
The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP.
Math. Oper. Res., February, 2023
CoRR, 2023
Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023
Proceedings of the 54th ACM Technical Symposium on Computer Science Education, Volume 1, 2023
Proceedings of the Integer Programming and Combinatorial Optimization, 2023
2022
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.
Math. Oper. Res., 2022
Proceedings of the Integer Programming and Combinatorial Optimization, 2022
Proceedings of the Integer Programming and Combinatorial Optimization, 2022
2021
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
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021
2020
Oper. Res. Lett., 2020
Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP.
Oper. Res. Lett., 2020
Math. Oper. Res., 2020
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
2018
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem.
SIAM J. Optim., 2018
2017
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds.
SIAM J. Comput., 2017
Oper. Res. Lett., 2017
An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem.
ACM J. Exp. Algorithmics, 2017
INFORMS J. Comput., 2017
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem.
Algorithmica, 2017
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
Math. Program., 2015
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
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014
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
2012
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
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
Cambridge University Press, ISBN: 978-0-521-19527-0, 2011
2010
SIAM J. Comput., 2010
2009
Networks, 2009
Math. Program., 2009
Math. Oper. Res., 2009
Games Econ. Behav., 2009
2008
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
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
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
Proceedings of the Twelfth International World Wide Web Conference, 2003
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003
2002
A primal-dual schema based approximation algorithm for the element connectivity problem.
J. Algorithms, 2002
Algorithmica, 2002
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. Discret. Math., 2000
SIAM J. Comput., 2000
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
Math. Program., 1998
Comb., 1998
1997
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
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
Proceedings of the Integer Programming and Combinatorial Optimization, 1996
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
1995
SIAM J. Comput., 1995
Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.
J. ACM, 1995
Comb., 1995
1994
SIAM J. Discret. Math., 1994
Oper. Res. Lett., 1994
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994
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
1991
1990
Inf. Process. Lett., 1990