David P. Williamson

Generating author description...

All published works

Action	Title	Year	Authors
+	Max cut and semidefinite rank	2024	Renee Mirka David P. Williamson
+ PDF Chat	A Lower Bound for the Max Entropy Algorithm for TSP	2024	Billy Jin Nathan Klein David P. Williamson
+ PDF Chat	A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems	2023	Monika Henzinger Billy Jin Richard Peng David P. Williamson
+	GILP: An Interactive Tool for Visualizing the Simplex Algorithm	2023	Henry W. Robbins Samuel C. Gutekunst David B. Shmoys David P. Williamson
+ PDF Chat	Revisiting Garg's 2-Approximation Algorithm for the <i>k</i>-MST Problem in Graphs	2023	Emmett Breen Renee Mirka Zichen Wang David P. Williamson
+ PDF Chat	A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP	2023	Billy Jin Nathan Klein David P. Williamson
+	A Lower Bound for the Max Entropy Algorithm for TSP	2023	Billy Jin Nathan Klein David P. Williamson
+ PDF Chat	The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP	2022	Samuel C. Gutekunst David P. Williamson
+	Graph Coloring and Semidefinite Rank	2022	Renee Mirka Devin Smedira David P. Williamson
+ PDF Chat	Graph Coloring and Semidefinite Rank	2022	Renee Mirka Devin Smedira David P. Williamson
+	The Two-Stripe Symmetric Circulant TSP is in P	2022	Samuel C. Gutekunst Billy Jin David P. Williamson
+	GILP: An Interactive Tool for Visualizing the Simplex Algorithm	2022	Henry W. Robbins Samuel C Gutekunst Frans Schalekamp David B. Shmoys David P. Williamson
+	A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP	2022	Billy Jin Nathan Klein David P. Williamson
+ PDF Chat	Tight Bounds for Online Weighted Tree Augmentation	2021	Joseph Naor Seeun William Umboh David P. Williamson
+	Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows	2021	Monika Henzinger Billy Jin Richard Peng David P. Williamson
+ PDF Chat	Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps	2021	Samuel C. Gutekunst David P. Williamson
+ PDF Chat	Recursive Random Contraction Revisited	2021	David R. Karger David P. Williamson
+	Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows	2021	Monika Henzinger Billy Jin Richard Peng David P. Williamson
+ PDF Chat	Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time	2020	Iddo Drori Anant Kharkar William R. Sickinger Brandon Kates Qiang Ma Suwen Ge Eden Dolev Brenda Dietrich David P. Williamson Madeleine Udell
+	A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems.	2020	Monika Henzinger Billy Jin David P. Williamson
+ PDF Chat	Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching	2020	Billy Jin David P. Williamson
+	Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time	2020	Iddo Drori Anant Kharkar William R. Sickinger Brandon Kates Qiang Ma Suwen Ge Eden Dolev Brenda Dietrich David P. Williamson Madeleine Udell
+ PDF Chat	Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP	2020	Samuel C. Gutekunst David P. Williamson
+ PDF Chat	Easy capacitated facility location problems, with connections to lot-sizing	2020	Alice Paul David P. Williamson
+	Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model	2020	Billy Jin David P. Williamson
+	Recursive Random Contraction Revisited.	2020	David R. Karger David P. Williamson
+	The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP	2020	Samuel C. Gutekunst David P. Williamson
+	A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems	2020	Monika Henzinger Billy Jin David P. Williamson
+	Recursive Random Contraction Revisited	2020	David R. Karger David P. Williamson
+	Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time	2020	Iddo Drori Anant Kharkar William R. Sickinger Brandon Kates Qiang Ma Suwen Ge Eden Dolev Brenda Dietrich David P. Williamson Madeleine Udell
+	Maximum Flow Algorithms	2019	David P. Williamson
+	Index	2019	David P. Williamson
+	Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP	2019	Samuel C. Gutekunst David P. Williamson
+	Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.	2019	Samuel C. Gutekunst David P. Williamson
+	Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem	2019	Samuel C. Gutekunst David P. Williamson
+	Tight Bounds for Online Weighted Tree Augmentation	2019	Joseph Joseph Naor Seeun William Umboh David P. Williamson
+ PDF Chat	Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem	2019	Samuel C. Gutekunst David P. Williamson
+	Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP	2019	Samuel C. Gutekunst David P. Williamson
+	Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps	2019	Samuel C. Gutekunst David P. Williamson
+	Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem	2019	Samuel C. Gutekunst David P. Williamson
+ PDF Chat	The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem	2018	Samuel C. Gutekunst David P. Williamson
+ PDF Chat	Online Constrained Forest and Prize-Collecting Network Design	2017	Jiawei Qian Seeun William Umboh David P. Williamson
+	The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem	2017	Samuel C. Gutekunst David P. Williamson
+ PDF Chat	Rank aggregation: New bounds for MCx	2017	Daniel Freund David P. Williamson
+ PDF Chat	An Experimental Evaluation of the Best-of-Many Christofides’ Algorithm for the Traveling Salesman Problem	2017	Kyle Genova David P. Williamson
+	Online Constrained Forest and Prize-Collecting Network Design	2017	Jiawei Qian Seeun William Umboh David P. Williamson
+	The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem	2017	Samuel C. Gutekunst David P. Williamson
+	Rank Aggregation: New Bounds for MCx	2015	Daniel Freund David P. Williamson
+ PDF Chat	Maximizing a Submodular Function with Viability Constraints	2015	Wolfgang Dvořák Monika Henzinger David P. Williamson
+	MC4, Copeland and restart probabilities.	2015	Daniel Freund David P. Williamson
+ PDF Chat	An Experimental Evaluation of the Best-of-Many Christofides’ Algorithm for the Traveling Salesman Problem	2015	Kyle Genova David P. Williamson
+	An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem	2015	Kyle Genova David P. Williamson
+	Rank Aggregation: New Bounds for MCx	2015	Daniel Freund David P. Williamson
+ PDF Chat	On the integrality gap of the subtour LP for the 1,2-TSP	2014	Jiawei Qian Frans Schalekamp David P. Williamson Anke van Zuylen
+ PDF Chat	Maximizing a Submodular Function with Viability Constraints	2013	Wolfgang Dvořák Monika Henzinger David P. Williamson
+	On Some Recent MAX SAT Approximation Algorithms	2013	Matthias Poloczek David P. Williamson Anke van Zuylen
+	A proof of the Boyd-Carr conjecture	2012	Frans Schalekamp David P. Williamson Anke van Zuylen
+ PDF Chat	A Proof of the Boyd-Carr Conjecture	2012	Frans Schalekamp David P. Williamson Anke van Zuylen
+ PDF Chat	On the Integrality Gap of the Subtour LP for the 1,2-TSP	2012	Jiawei Qian Frans Schalekamp David P. Williamson Anke van Zuylen
+ PDF Chat	A note on the generalized min-sum set cover problem	2011	Martin Skutella David P. Williamson
+	Further Uses of Randomized Rounding of Semidefinite Programs	2011	David P. Williamson David B. Shmoys
+	Linear Programming	2011	David P. Williamson David B. Shmoys
+	Deterministic Rounding of Linear Programs	2011	David P. Williamson David B. Shmoys
+	Randomized Rounding of Semidefinite Programs	2011	David P. Williamson David B. Shmoys
+	The Primal-Dual Method	2011	David P. Williamson David B. Shmoys
+	Cuts and Metrics	2011	David P. Williamson David B. Shmoys
+	Further Uses of Random Sampling and Randomized Rounding of Linear Programs	2011	David P. Williamson David B. Shmoys
+	On the Integrality Gap of the Subtour LP for the 1,2-TSP	2011	Jiawei Qian Frans Schalekamp David P. Williamson Anke van Zuylen
+	A Proof of the Boyd-Carr Conjecture	2011	Frans Schalekamp David P. Williamson Anke van Zuylen
+	A note on the generalized min-sum set cover problem	2011	Martin Skutella David P. Williamson
+	A simple GAP-canceling algorithm for the generalized maximum flow problem	2007	Mateo Restrepo David P. Williamson
+	The primal-dual method for approximation algorithms	2002	David P. Williamson
+	Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming	2001	Michel X. Goemans David P. Williamson
+	Adversarial queuing theory	2001	Allan Borodin Jon Kleinberg Prabhakar Raghavan Madhu Sudan David P. Williamson
+	A Short Primer on the Primal-Dual Method for Approximation Algorithms (Algorithm Engineering as a New Paradigm)	2001	David P. Williamson
+	Bayesian decision procedures based on logistic regression models for dose-finding studies	1998	John Whitehead David P. Williamson
+	Two-dimensional Gantt charts and a scheduling algorithm of Lawler	1998	Michel X. Goemans David P. Williamson
+ PDF Chat	Approximation algorithms	1997	Andreas S. Schulz David B. Shmoys David P. Williamson
+	Gadgets, approximation, and linear programming: Improved hardness results for cut and satisfiability problems	1997	David P. Williamson
+	A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction	1997	Sanjeev Khanna Madhu Sudan David P. Williamson
+	On the number of small cuts in a graph	1996	Monika Henzinger David P. Williamson
+	Primal-Dual Approximation Algorithms for Feedback Problems	1996	Michel X. Goemans David P. Williamson
+ PDF Chat	Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming	1995	Michel X. Goemans David P. Williamson

Common Coauthors

Coauthor	Papers Together
Samuel C. Gutekunst	16
Billy Jin	12
David B. Shmoys	10
Monika Henzinger	8
Frans Schalekamp	7
Anke van Zuylen	7
Jiawei Qian	5
Daniel Freund	4
Nathan Klein	4
Seeun William Umboh	4
Renee Mirka	4
Michel X. Goemans	4
Anant Kharkar	3
Iddo Drori	3
Brenda Dietrich	3
Suwen Ge	3
Eden Dolev	3
David R. Karger	3
Kyle Genova	3
Brandon Kates	3
Madeleine Udell	3
William R. Sickinger	3
Richard Peng	3
Wolfgang Dvořák	2
Qiang Ma	2
Martin Skutella	2
Devin Smedira	2
Madhu Sudan	2
Henry W. Robbins	2
Joseph Naor	1
Mateo Restrepo	1
Sanjeev Khanna	1
Naor	1
Jon Kleinberg	1
Allan Borodin	1
Matthias Poloczek	1
Emmett Breen	1
Joseph Joseph	1
Prabhakar Raghavan	1
Alice Paul	1
Samuel C Gutekunst	1
John Whitehead	1
Qiang Ma	1
Zichen Wang	1
Andreas S. Schulz	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+ PDF Chat	A Randomized Rounding Approach to the Traveling Salesman Problem	2011	Shayan Oveis Gharan Amin Saberi Mohit Singh	9
+ PDF Chat	On Semidefinite Programming Relaxations of the Traveling Salesman Problem	2009	Etienne de Klerk Dmitrii V. Ṗasechnik Renata Sotirov	8
+	Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs	2014	András Sebő Jens Vygen	7
+ PDF Chat	Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry	2010	Etienne de Klerk Renata Sotirov	7
+	New inapproximability bounds for TSP	2015	Marek Karpiński Michael Lampis Richard Schmied	7
+ PDF Chat	Approximating Graphic TSP by Matchings	2011	Tobias Moemke Ola Svensson	7
+	13/9-approximation for Graphic TSP	2011	Marcin Mucha	6
+ PDF Chat	The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem	2018	Samuel C. Gutekunst David P. Williamson	6
+ PDF Chat	On the shortest spanning subtree of a graph and the traveling salesman problem	1956	Joseph B. Kruskal	5
+	Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization	1995	Farid Alizadeh	4
+ PDF Chat	Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming	1995	Michel X. Goemans David P. Williamson	4
+ PDF Chat	Computing Maximum Flow with Augmenting Electrical Flows	2016	Aleksander Mądry	4
+ PDF Chat	Spectral Sparsification of Graphs	2011	Daniel A. Spielman Shang‐Hua Teng	4
+	Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs	2011	Paul F. Christiano Jonathan A. Kelner Aleksander Mądry Daniel A. Spielman Shang‐Hua Teng	4
+	Semidefinite Programming Methods for the Symmetric Traveling Salesman Problem	1999	Dragoš Cvetković Mirjana Čangalović Vera Kovačevíc-Vujčić	4
+	A 4/3-approximation for TSP on cubic 3-edge-connected graphs	2011	Nishita Aggarwal Naveen Garg Swati Gupta	3
+ PDF Chat	Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture	2015	Monika Henzinger Sebastian Krinninger Danupon Nanongkai Thatchaphol Saranurak	3
+	On the Shannon capacity of a graph	1979	László Lovász	3
+	Introduction to Algorithms	1991	V. J. Rayward‐Smith Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest	3
+	A polynomial dual simplex algorithm for the generalized circulation problem	2002	Donald Goldfarb Zhiying Jin Yiqing Lin	3
+	A proof of the Boyd-Carr conjecture	2012	Frans Schalekamp David P. Williamson Anke van Zuylen	3
+	Optimum flows in general communication networks	1967	Kenji Onaga	3
+	Efficient algorithms for certain satisfiability and linear programming problems	1981	Bengt Aspvall	3
+	Practical graph isomorphism, II	2013	Brendan D. McKay Adolfo Piperno	3
+	Linear Programming and Extensions	1963	George B. Dantzig	3
+	Linear Inequalities and Related Systems.	1956	George B. Dantzig Harold W. Kuhn A. W. Tucker	3
+	Online network design algorithms via hierarchical decompositions	2015	Seeun William Umboh	3
+ PDF Chat	On the Metric $s$--$t$ Path Traveling Salesman Problem	2015	Zhihan Gao	3
+ PDF Chat	A simple, combinatorial algorithm for solving SDD systems in nearly-linear time	2013	Jonathan A. Kelner Lorenzo Orecchia Aaron Sidford Zeyuan Allen Zhu	3
+	A Faster Combinatorial Algorithm for the Generalized Circulation Problem	1996	Donald Goldfarb Zhiying Jin	3
+	Toeplitz and circulant matrices	1977	Robert M. Gray	3
+	Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.	2019	Samuel C. Gutekunst David P. Williamson	3
+	The Travelling Salesman Problem in symmetric circulant matrices with two stripes	2008	Ivan Gerace Federico Greco	2
+	Handbook of Mathematical Formulas and Integrals	1996	Alan Jeffrey Robert H. Romer	2
+ PDF Chat	Statistical mechanics of complex networks	2002	Réka Albert Albert‐László Barabási	2
+	Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice	2002	Daniel Bienstock	2
+	Generating Random Regular Graphs Quickly	1999	Angelika Steger N. C. Wormald	2
+ PDF Chat	Approximate graph coloring by semidefinite programming	1998	David R. Karger Rajeev Motwani Madhu Sudan	2
+	Polynomial-time primal simplex algorithms for the minimum cost network flow problem	1992	Donald Goldfarb Jianxiu Hao	2
+	An efficient scaling procedure for gain networks	1976	Klaus Truemper	2
+	Generating random regular graphs	2003	Jeong Han Kim Van H. Vu	2
+	A truncated primal-infeasible dual-feasible network interior point method	2000	Luís Portugal Maurício G. C. Resende Geraldo Veiga J. J. J�dice	2
+ PDF Chat	Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems	2004	Daniel A. Spielman Shang‐Hua Teng	2
+ PDF Chat	On the integrality gap of the subtour LP for the 1,2-TSP	2014	Jiawei Qian Frans Schalekamp David P. Williamson Anke van Zuylen	2
+	Note on Weintraub’s Minimum-Cost Circulation Algorithm	1989	Francisco Barahona Éva Tardos	2
+ PDF Chat	Spectral sparsification of graphs	2013	Joshua Batson Daniel A. Spielman Nikhil Srivastava Shang‐Hua Teng	2
+	On the equivalence of some generalized network problems to pure network problems	1973	Fred Glover Darwin Klingman	2
+	Eigenvalue Bounds Versus Semidefinite Relaxations for the Quadratic Assignment Problem	2000	Kurt M. Anstreicher	2
+ PDF Chat	Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems	2014	Daniel A. Spielman Shang‐Hua Teng	2
+	An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs	2001	Jean B. Lasserre	2