David P. Williamson

166 papers A* 27A 5B 22C 3Journal 102Unranked 6

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	The two-stripe symmetric circulant TSP is in P. Math. Program. Samuel C. Gutekunst, Billy Jin, David P. Williamson
2025	J	`jnl`	A $\frac{4}{3}$-approximation algorithm for half-integral cycle cut instances of the TSP. Math. Program. Billy Jin, Nathan Klein, David P. Williamson
2024	B	`conf`	A Lower Bound for the Max Entropy Algorithm for TSP. IPCO Billy Jin, Nathan Klein, David P. Williamson
2024	J	`jnl`	Graph coloring and semidefinite rank. Math. Program. Renee Mirka, Devin Smedira, David P. Williamson
2024	J	`jnl`	Max cut and semidefinite rank. Oper. Res. Lett. Renee Mirka, David P. Williamson
2023	B	`conf`	A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. IPCO Billy Jin, Nathan Klein, David P. Williamson
2023	A	`conf`	A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. ITCS Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson
2023	J	`jnl`	A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. Algorithmica Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson
2023	J	`jnl`	A Lower Bound for the Max Entropy Algorithm for TSP. CoRR Billy Jin, Nathan Klein, David P. Williamson
2023	J	`jnl`	An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut. ACM J. Exp. Algorithmics Renee Mirka, David P. Williamson
2023	J	`jnl`	Erratum to "Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems". Math. Oper. Res. Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson
2023	J	`jnl`	Fluid Approximations for Revenue Management Under High-Variance Demand. Manag. Sci. Yicheng Bai, Omar El Housni, Billy Jin, Paat Rusmevichientong, Huseyin Topaloglu, David P. Williamson
2023	—	`conf`	GILP: An Interactive Tool for Visualizing the Simplex Algorithm. SIGCSE (1) Henry W. Robbins, Samuel C. Gutekunst, David B. Shmoys, David P. Williamson
2023	—	`conf`	Revisiting Garg's 2-Approximation Algorithm for the SOSA Emmett Breen, Renee Mirka, Zichen Wang, David P. Williamson
2023	J	`jnl`	Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs. CoRR Emmett Breen, Renee Mirka, Zichen Wang, David P. Williamson
2023	J	`jnl`	Special Issue: Integer Programming and Combinatorial Optimization (IPCO) 2021. Math. Program. Santanu S. Dey, Mohit Singh, David P. Williamson
2023	J	`jnl`	The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP. Math. Oper. Res. Samuel C. Gutekunst, David P. Williamson
2022	J	`jnl`	A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. CoRR Billy Jin, Nathan Klein, David P. Williamson
2022	B	`conf`	An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut. SEA Renee Mirka, David P. Williamson
2022	J	`jnl`	GILP: An Interactive Tool for Visualizing the Simplex Algorithm. CoRR Henry W. Robbins, Samuel C. Gutekunst, Frans Schalekamp, David B. Shmoys, David P. Williamson
2022	B	`conf`	Graph Coloring and Semidefinite Rank. IPCO Renee Mirka, Devin Smedira, David P. Williamson
2022	J	`jnl`	Graph Coloring and Semidefinite Rank. CoRR Renee Mirka, Devin Smedira, David P. Williamson
2022	J	`jnl`	Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps. Math. Oper. Res. Samuel C. Gutekunst, David P. Williamson
2022	B	`conf`	The Two-Stripe Symmetric Circulant TSP is in P. IPCO Samuel C. Gutekunst, Billy Jin, David P. Williamson
2022	J	`jnl`	The Two-Stripe Symmetric Circulant TSP is in P. CoRR Samuel C. Gutekunst, Billy Jin, David P. Williamson
2022	J	`jnl`	Tight Bounds for Online Weighted Tree Augmentation. Algorithmica Joseph (Seffi) Naor, Seeun William Umboh, David P. Williamson
2021	J	`jnl`	Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows. CoRR Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson
2021	—	`conf`	Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model. WINE Billy Jin, David P. Williamson
2021	B	`ed.`	Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19-21, 2021, Proceedings IPCO Mohit Singh, David P. Williamson
2021	—	`conf`	Recursive Random Contraction Revisited. SOSA David R. Karger, David P. Williamson
2020	J	`jnl`	A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems. CoRR Monika Henzinger, Billy Jin, David P. Williamson
2020	J	`jnl`	Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems. Math. Oper. Res. Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson
2020	J	`jnl`	Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing. CoRR Alice Paul, David P. Williamson
2020	J	`jnl`	Easy capacitated facility location problems, with connections to lot-sizing. Oper. Res. Lett. Alice Paul, David P. Williamson
2020	J	`jnl`	Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching. CoRR Billy Jin, David P. Williamson
2020	C	`conf`	Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time. ICMLA Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, Madeleine Udell
2020	J	`jnl`	Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time. CoRR Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, Madeleine Udell
2020	J	`jnl`	Recursive Random Contraction Revisited. CoRR David R. Karger, David P. Williamson
2020	J	`jnl`	Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP. Oper. Res. Lett. Samuel C. Gutekunst, David P. Williamson
2020	J	`jnl`	The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP. CoRR Samuel C. Gutekunst, David P. Williamson
2019	J	`jnl`	Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem. CoRR Samuel C. Gutekunst, David P. Williamson
2019	J	`jnl`	Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem. SIAM J. Discret. Math. Samuel C. Gutekunst, David P. Williamson
2019	J	`jnl`	Rank aggregation: New bounds for MCx. Discret. Appl. Math. Daniel Freund, David P. Williamson
2019	J	`jnl`	Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps. CoRR Samuel C. Gutekunst, David P. Williamson
2019	J	`jnl`	Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP. CoRR Samuel C. Gutekunst, David P. Williamson
2019	A*	`conf`	Tight Bounds for Online Weighted Tree Augmentation. ICALP Joseph (Seffi) Naor, Seeun William Umboh, David P. Williamson
2019	J	`jnl`	Tight Bounds for Online Weighted Tree Augmentation. CoRR Joseph Naor, Seeun William Umboh, David P. Williamson
2018	J	`jnl`	Online Constrained Forest and Prize-Collecting Network Design. Algorithmica Jiawei Qian, Seeun William Umboh, David P. Williamson
2018	J	`jnl`	Simple Approximation Algorithms for Balanced MAX 2SAT. Algorithmica Alice Paul, Matthias Poloczek, David P. Williamson
2018	J	`jnl`	The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem. SIAM J. Optim. Samuel C. Gutekunst, David P. Williamson
2017	J	`jnl`	An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem. ACM J. Exp. Algorithmics Matthias Poloczek, David P. Williamson
2017	J	`jnl`	An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem. Algorithmica Kyle Genova, David P. Williamson
2017	J	`jnl`	Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds. SIAM J. Comput. Matthias Poloczek, Georg Schnitger, David P. Williamson, Anke van Zuylen
2017	J	`jnl`	Greedy algorithms for the single-demand facility location problem. Oper. Res. Lett. Sin-Shuen Cheung, David P. Williamson
2017	J	`jnl`	Maximizing a Submodular Function with Viability Constraints. Algorithmica Wolfgang Dvorák, Monika Henzinger, David P. Williamson
2017	J	`jnl`	Online Constrained Forest and Prize-Collecting Network Design. CoRR Jiawei Qian, Seeun William Umboh, David P. Williamson
2017	J	`jnl`	Pricing Problems Under the Nested Logit Model with a Quality Consistency Constraint. INFORMS J. Comput. James M. Davis, Huseyin Topaloglu, David P. Williamson
2017	A	`conf`	Prize-Collecting TSP with a Budget Constraint. ESA Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson
2017	J	`jnl`	The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem. CoRR Samuel C. Gutekunst, David P. Williamson
2016	J	`jnl`	A Randomized O(log n)-Competitive Algorithm for the Online Connected Facility Location Problem. Algorithmica Mário César San Felice, David P. Williamson, Orlando Lee
2016	B	`conf`	An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem. SEA Matthias Poloczek, David P. Williamson
2016	J	`jnl`	Maximizing a Submodular Function with Viability Constraints. CoRR Wolfgang Dvorák, Monika Henzinger, David P. Williamson
2016	B	`conf`	Simple Approximation Algorithms for Balanced MAX 2SAT. LATIN Alice Paul, Matthias Poloczek, David P. Williamson
2015	J	`jnl`	A 3/2-approximation algorithm for some minimum-cost graph problems. Math. Program. Basile Couëtoux, James M. Davis, David P. Williamson
2015	A	`conf`	An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem. ESA Kyle Genova, David P. Williamson
2015	J	`jnl`	An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem. CoRR Kyle Genova, David P. Williamson
2015	J	`jnl`	Assortment optimization over time. Oper. Res. Lett. James M. Davis, Huseyin Topaloglu, David P. Williamson
2015	C	`conf`	MC4, Copeland and restart probabilities. CTW Daniel Freund, David P. Williamson
2015	J	`jnl`	On the integrality gap of the subtour LP for the 1, 2-TSP. Math. Program. Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen
2015	J	`jnl`	Rank Aggregation: New Bounds for MCx. CoRR Daniel Freund, David P. Williamson
2015	J	`jnl`	The Online Prize-Collecting Facility Location Problem. Electron. Notes Discret. Math. Mário César San Felice, Sin-Shuen Cheung, Orlando Lee, David P. Williamson
2014	J	`jnl`	2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture. Math. Oper. Res. Frans Schalekamp, David P. Williamson, Anke van Zuylen
2014	B	`conf`	On Some Recent Approximation Algorithms for MAX SAT. LATIN Matthias Poloczek, David P. Williamson, Anke van Zuylen
2014	J	`jnl`	Popular ranking. Discret. Appl. Math. Anke van Zuylen, Frans Schalekamp, David P. Williamson
2014	B	`conf`	The Online Connected Facility Location Problem. LATIN Mário César San Felice, David P. Williamson, Orlando Lee
2013	J	`jnl`	An Experimental Evaluation of Incremental and Hierarchical ACM J. Exp. Algorithmics Chandrashekhar Nagarajan, David P. Williamson
2013	A	`conf`	Maximizing a Submodular Function with Viability Constraints. ESA Wolfgang Dvorák, Monika Henzinger, David P. Williamson
2013	J	`jnl`	Offline and online facility leasing. Discret. Optim. Chandrashekhar Nagarajan, David P. Williamson
2013	J	`jnl`	On Some Recent MAX SAT Approximation Algorithms. CoRR Matthias Poloczek, David P. Williamson, Anke van Zuylen
2012	A	`conf`	A Dual-Fitting $\frac{3}{2}$ -Approximation Algorithm for Some Minimum-Cost Graph Problems. ESA James M. Davis, David P. Williamson
2012	A*	`conf`	A proof of the Boyd-Carr conjecture. SODA Frans Schalekamp, David P. Williamson, Anke van Zuylen
2012	B	`conf`	On the Integrality Gap of the Subtour LP for the 1, 2-TSP. LATIN Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen
2011	J	`jnl`	A Proof of the Boyd-Carr Conjecture CoRR Frans Schalekamp, David P. Williamson, Anke van Zuylen
2011	J	`jnl`	A note on the generalized min-sum set cover problem CoRR Martin Skutella, David P. Williamson
2011	J	`jnl`	A note on the generalized min-sum set cover problem. Oper. Res. Lett. Martin Skutella, David P. Williamson
2011	—	`conf`	An ICALP (1) Jiawei Qian, David P. Williamson
2011	B	`conf`	An Experimental Evaluation of Incremental and Hierarchical SEA Chandrashekhar Nagarajan, David P. Williamson
2011	J	`jnl`	On the Integrality Gap of the Subtour LP for the 1,2-TSP CoRR Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen
2011	C	`conf`	Popular Ranking. CTW Anke van Zuylen, Frans Schalekamp, David P. Williamson
2011	—	`book`	The Design of Approximation Algorithms. David P. Williamson, David B. Shmoys
2010	J	`jnl`	A General Approach for Incremental Approximation and Hierarchical Clustering. SIAM J. Comput. Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson
2009	J	`jnl`	A simple GAP-canceling algorithm for the generalized maximum flow problem. Math. Program. Mateo Restrepo, David P. Williamson
2009	J	`jnl`	Approximating the smallest Networks Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson
2009	J	`jnl`	Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems. Math. Oper. Res. Anke van Zuylen, David P. Williamson
2009	J	`jnl`	Stackelberg thresholds in network routing games or the value of altruism. Games Econ. Behav. Yogeshwer Sharma, David P. Williamson
2008	J	`jnl`	A Faster, Better Approximation Algorithm for the Minimum Latency Problem. SIAM J. Comput. Aaron Archer, Asaf Levin, David P. Williamson
2008	B	`conf`	Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements. WAOA Chandrashekhar Nagarajan, Yogeshwer Sharma, David P. Williamson
2008	B	`conf`	Offline and Online Facility Leasing. IPCO Chandrashekhar Nagarajan, David P. Williamson
2007	J	`jnl`	A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Oper. Res. Lett. David P. Williamson, Anke van Zuylen
2007	A*	`conf`	Approximation algorithms for prize collecting forest problems with submodular penalty functions. SODA Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson
2007	B	`conf`	Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems. WAOA Anke van Zuylen, David P. Williamson
2007	A*	`conf`	Deterministic pivoting algorithms for constrained ranking and clustering problems. SODA Anke van Zuylen, Rajneesh Hegde, Kamal Jain, David P. Williamson
2007	B	`ed.`	Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings IPCO Matteo Fischetti, David P. Williamson
2007	A*	`conf`	Stackelberg thresholds in network routing games or the value of altruism. EC Yogeshwer Sharma, David P. Williamson
2006	A*	`conf`	A general approach for incremental approximation and hierarchical clustering. SODA Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson
2006	A*	`conf`	A simple GAP-canceling algorithm for the generalized maximum flow problem. SODA Mateo Restrepo, David P. Williamson
2006	A*	`conf`	An adaptive algorithm for selecting profitable keywords for search-based advertising services. EC Paat Rusmevichientong, David P. Williamson
2006	J	`jnl`	Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. Syst. Sci. Lisa Fleischer, Kamal Jain, David P. Williamson
2006	J	`jnl`	On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems. Theor. Comput. Sci. R. N. Uma, Joel Wein, David P. Williamson
2005	A*	`conf`	Approximating the smallest SODA Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson
2005	J	`jnl`	Improved approximation algorithms for capacitated facility location problems. Math. Program. Fabián A. Chudak, David P. Williamson
2004	J	`jnl`	Approximate Math. Program. Fabián A. Chudak, Tim Roughgarden, David P. Williamson
2004	J	`jnl`	Approximation algorithms for M J. Comput. Syst. Sci. Michel X. Goemans, David P. Williamson
2003	A*	`conf`	Faster approximation algorithms for the minimum latency problem. SODA Aaron Archer, David P. Williamson
2003	A*	`conf`	Searching the workplace web. WWW Ronald Fagin, Ravi Kumar, Kevin S. McCurley, Jasmine Novak, D. Sivakumar, John A. Tomlin, David P. Williamson
2002	J	`jnl`	A primal-dual schema based approximation algorithm for the element connectivity problem. J. Algorithms Kamal Jain, Ion I. Mandoiu, Vijay V. Vazirani, David P. Williamson
2002	J	`jnl`	Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. Algorithmica R. Ravi, David P. Williamson
2002	A*	`conf`	Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems. SODA R. Ravi, David P. Williamson
2002	J	`jnl`	Improved Approximation Algorithms for MAX SAT. J. Algorithms Takao Asano, David P. Williamson
2002	J	`jnl`	The primal-dual method for approximation algorithms. Math. Program. David P. Williamson
2001	J	`jnl`	Adversarial queuing theory. J. ACM Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
2001	A*	`conf`	An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem. FOCS Lisa Fleischer, Kamal Jain, David P. Williamson
2001	B	`conf`	Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation. IPCO Fabián A. Chudak, Tim Roughgarden, David P. Williamson
2001	A*	`conf`	Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. STOC Michel X. Goemans, David P. Williamson
2000	J	`jnl`	A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. Oper. Res. Lett. Michel X. Goemans, Joel Wein, David P. Williamson
2000	J	`jnl`	Gadgets, Approximation, and Linear Programming. SIAM J. Comput. Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
2000	A*	`conf`	Improved approximation algorithms for MAX SAT. SODA Takao Asano, David P. Williamson
2000	J	`jnl`	Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. SIAM J. Comput. Alok Aggarwal, Jon M. Kleinberg, David P. Williamson
2000	J	`jnl`	The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson
2000	J	`jnl`	Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SIAM J. Discret. Math. Michel X. Goemans, David P. Williamson
1999	A*	`conf`	A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem. SODA Kamal Jain, Ion I. Mandoiu, Vijay V. Vazirani, David P. Williamson
1999	B	`conf`	Improved Approximation Algorithms for Capacitated Facility Location Problems. IPCO Fabián A. Chudak, David P. Williamson
1999	A*	`conf`	Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SODA Michel X. Goemans, David P. Williamson
1998	J	`jnl`	A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson
1998	J	`jnl`	An efficient approximation algorithm for the survivable network design problem. Math. Program. Harold N. Gabow, Michel X. Goemans, David P. Williamson
1998	J	`jnl`	Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs. Comb. Michel X. Goemans, David P. Williamson
1997	A*	`conf`	A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. STOC Sanjeev Khanna, Madhu Sudan, David P. Williamson
1997	J	`jnl`	An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. Algorithmica R. Ravi, David P. Williamson
1997	B	`conf`	Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture). WG David P. Williamson
1997	J	`jnl`	Short Shop Schedules. Oper. Res. David P. Williamson, Leslie A. Hall, J. A. Hoogeveen, Cor A. J. Hurkens, Jan Karel Lenstra, Sergey Vasil'evich Sevast'janov, David B. Shmoys
1996	J	`jnl`	A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction Electron. Colloquium Comput. Complex. Sanjeev Khanna, Madhu Sudan, David P. Williamson
1996	A*	`conf`	Adversarial Queueing Theory. STOC Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
1996	J	`jnl`	Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. INFORMS J. Comput. David P. Williamson, Michel X. Goemans
1996	A*	`conf`	Gadgets, Approximation, and Linear Programming (extended abstract). FOCS Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
1996	A*	`conf`	Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. STOC Alok Aggarwal, Jon M. Kleinberg, David P. Williamson
1996	J	`jnl`	On the Number of Small Cuts in a Graph. Inf. Process. Lett. Monika Henzinger, David P. Williamson
1996	B	`conf`	Primal-Dual Approximation Algorithms for Feedback Problems. IPCO Michel X. Goemans, David P. Williamson
1995	J	`jnl`	A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput. Michel X. Goemans, David P. Williamson
1995	J	`jnl`	A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. Comb. David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani
1995	J	`jnl`	Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM Michel X. Goemans, David P. Williamson
1995	J	`jnl`	Scheduling Parallel Machines On-Line. SIAM J. Comput. David B. Shmoys, Joel Wein, David P. Williamson
1994	A*	`conf`	.879-approximation algorithms for MAX CUT and MAX 2SAT. STOC Michel X. Goemans, David P. Williamson
1994	J	`jnl`	Approximating minimum-cost graph problems with spanning tree edges. Oper. Res. Lett. Michel X. Goemans, David P. Williamson
1994	A*	`conf`	Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. SODA David P. Williamson, Michel X. Goemans
1994	A*	`conf`	Improved Approximation Algorithms for Network Design Problems. SODA Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, David P. Williamson
1994	J	`jnl`	New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem. SIAM J. Discret. Math. Michel X. Goemans, David P. Williamson
1993	B	`conf`	A new \frac34-approximation algorithm for MAX SAT. IPCO Michel X. Goemans, David P. Williamson
1993	J	`jnl`	A note on the prize collecting traveling salesman problem. Math. Program. Daniel Bienstock, Michel X. Goemans, David Simchi-Levi, David P. Williamson
1993	A*	`conf`	A primal-dual approximation algorithm for generalized Steiner network problems. STOC David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani
1993	B	`conf`	An efficient approximation algorithm for the survivable network design problem. IPCO Harold N. Gabow, Michel X. Goemans, David P. Williamson
1992	A*	`conf`	A General Approximation Technique for Constrained Forest Problems. SODA Michel X. Goemans, David P. Williamson
1992	J	`jnl`	Analysis of the Held-Karp lower bound for the asymmetric TSP. Oper. Res. Lett. David P. Williamson
1991	J	`jnl`	Permutation vs. non-permutation flow shop schedules. Oper. Res. Lett. Chris N. Potts, David B. Shmoys, David P. Williamson
1991	A*	`conf`	Scheduling Parallel Machines On-Line FOCS David B. Shmoys, Joel Wein, David P. Williamson
1991	—	`conf`	Scheduling Parallel Machines On-line. On-Line Algorithms David B. Shmoys, Joel Wein, David P. Williamson
1990	J	`jnl`	Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application. Inf. Process. Lett. David B. Shmoys, David P. Williamson