David P. Williamson

James M. Davis, David P. Williamson: A Dual-Fitting $\frac{3}{2}$ -Approximation Algorithm for Some Minimum-Cost Graph Problems. ESA 2012: 373-382

Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen: On the Integrality Gap of the Subtour LP for the 1, 2-TSP. LATIN 2012: 606-617

Frans Schalekamp, David P. Williamson, Anke van Zuylen: A proof of the Boyd-Carr conjecture. SODA 2012: 1477-1486

David P. Williamson, David B. Shmoys: The Design of Approximation Algorithms. Cambridge University Press 2011, isbn 978-0-521-19527-0, pp. I-XI, 1-504

Martin Skutella, David P. Williamson: A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39(6): 433-436 (2011)

Anke van Zuylen, Frans Schalekamp, David P. Williamson: Popular Ranking. CTW 2011: 267-270

Jiawei Qian, David P. Williamson: An O(logn)-Competitive Algorithm for Online Constrained Forest Problems. ICALP (1) 2011: 37-48

Chandrashekhar Nagarajan, David P. Williamson: An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms. SEA 2011: 169-180

Frans Schalekamp, David P. Williamson, Anke van Zuylen: A Proof of the Boyd-Carr Conjecture. CoRR abs/1107.1628 (2011)

Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen: On the Integrality Gap of the Subtour LP for the 1,2-TSP. CoRR abs/1107.1630 (2011)

Martin Skutella, David P. Williamson: A note on the generalized min-sum set cover problem. CoRR abs/1107.2033 (2011)

Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson: A General Approach for Incremental Approximation and Hierarchical Clustering. SIAM J. Comput. 39(8): 3633-3669 (2010)

Yogeshwer Sharma, David P. Williamson: Stackelberg thresholds in network routing games or the value of altruism. Games and Economic Behavior 67(1): 174-190 (2009)

Anke van Zuylen, David P. Williamson: Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems. Math. Oper. Res. 34(3): 594-620 (2009)

Mateo Restrepo, David P. Williamson: A simple GAP-canceling algorithm for the generalized maximum flow problem. Math. Program. 118(1): 47-74 (2009)

Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson: Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks 53(4): 345-357 (2009)

Aaron Archer, Asaf Levin, David P. Williamson: A Faster, Better Approximation Algorithm for the Minimum Latency Problem. SIAM J. Comput. 37(5): 1472-1498 (2008)

Chandrashekhar Nagarajan, David P. Williamson: Offline and Online Facility Leasing. IPCO 2008: 303-315

Chandrashekhar Nagarajan, Yogeshwer Sharma, David P. Williamson: Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements. WAOA 2008: 174-187

David P. Williamson, Anke van Zuylen: A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Oper. Res. Lett. 35(6): 707-712 (2007)

Yogeshwer Sharma, David P. Williamson: Stackelberg thresholds in network routing games or the value of altruism. ACM Conference on Electronic Commerce 2007: 93-102

Anke van Zuylen, Rajneesh Hegde, Kamal Jain, David P. Williamson: Deterministic pivoting algorithms for constrained ranking and clustering problems. SODA 2007: 405-414

Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson: Approximation algorithms for prize collecting forest problems with submodular penalty functions. SODA 2007: 1275-1284

Anke van Zuylen, David P. Williamson: Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems. WAOA 2007: 260-273

Matteo Fischetti, David P. Williamson (Eds.): Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings. Lecture Notes in Computer Science 4513, Springer 2007, isbn 978-3-540-72791-0

Lisa Fleischer, Kamal Jain, David P. Williamson: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. Syst. Sci. 72(5): 838-867 (2006)

R. N. Uma, Joel Wein, David P. Williamson: On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems. Theor. Comput. Sci. 361(2-3): 241-256 (2006)

Paat Rusmevichientong, David P. Williamson: An adaptive algorithm for selecting profitable keywords for search-based advertising services. ACM Conference on Electronic Commerce 2006: 260-269

Mateo Restrepo, David P. Williamson: A simple GAP-canceling algorithm for the generalized maximum flow problem. SODA 2006: 534-543

Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson: A general approach for incremental approximation and hierarchical clustering. SODA 2006: 1147-1156

Fabián A. Chudak, David P. Williamson: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102(2): 207-222 (2005)

Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson: Approximating the smallest k-edge connected spanning subgraph by LP-rounding. SODA 2005: 562-571

Michel X. Goemans, David P. Williamson: Approximation algorithms for M_AX-3-C_UT and other problems via complex semidefinite programming. J. Comput. Syst. Sci. 68(2): 442-470 (2004)

Fabián A. Chudak, Tim Roughgarden, David P. Williamson: Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Math. Program. 100(2): 411-421 (2004)

Aaron Archer, David P. Williamson: Faster approximation algorithms for the minimum latency problem. SODA 2003: 88-96

Ronald Fagin, Ravi Kumar, Kevin S. McCurley, Jasmine Novak, D. Sivakumar, John A. Tomlin, David P. Williamson: Searching the workplace web. WWW 2003: 366-375

R. Ravi, David P. Williamson: Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. Algorithmica 34(1): 98-107 (2002)

Takao Asano, David P. Williamson: Improved Approximation Algorithms for MAX SAT. J. Algorithms 42(1): 173-202 (2002)

Kamal Jain, Ion I. Mandoiu, Vijay V. Vazirani, David P. Williamson: A primal-dual schema based approximation algorithm for the element connectivity problem. J. Algorithms 45(1): 1-15 (2002)

R. Ravi, David P. Williamson: Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems. SODA 2002: 1000-1001

Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson: Adversarial queuing theory. J. ACM 48(1): 13-38 (2001)

Lisa Fleischer, Kamal Jain, David P. Williamson: An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem. FOCS 2001: 339-347

Fabián A. Chudak, Tim Roughgarden, David P. Williamson: Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation. IPCO 2001: 60-70

Michel X. Goemans, David P. Williamson: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. STOC 2001: 443-452

Michel X. Goemans, Joel Wein, David P. Williamson: A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. Oper. Res. Lett. 26(4): 149-154 (2000)

Alok Aggarwal, Jon M. Kleinberg, David P. Williamson: Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. SIAM J. Comput. 29(4): 1321-1333 (2000)

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson: Gadgets, Approximation, and Linear Programming. SIAM J. Comput. 29(6): 2074-2097 (2000)

Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson: The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. 30(6): 1863-1920 (2000)

Michel X. Goemans, David P. Williamson: Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SIAM J. Discrete Math. 13(3): 281-294 (2000)

Takao Asano, David P. Williamson: Improved approximation algorithms for MAX SAT. SODA 2000: 96-105

Fabián A. Chudak, David P. Williamson: Improved Approximation Algorithms for Capacitated Facility Location Problems. IPCO 1999: 99-113

Michel X. Goemans, David P. Williamson: Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SODA 1999: 366-375

Kamal Jain, Ion I. Mandoiu, Vijay V. Vazirani, David P. Williamson: A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem. SODA 1999: 484-489

Michel X. Goemans, David P. Williamson: Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs. Combinatorica 18(1): 37-59 (1998)

Harold N. Gabow, Michel X. Goemans, David P. Williamson: An efficient approximation algorithm for the survivable network design problem. Math. Program. 82: 13-40 (1998)

Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22(4-5): 111-118 (1998)

R. Ravi, David P. Williamson: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. Algorithmica 18(1): 21-43 (1997)

Sanjeev Khanna, Madhu Sudan, David P. Williamson: A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. STOC 1997: 11-20

David P. Williamson: Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture). WG 1997: 1

David P. Williamson, Michel X. Goemans: Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. INFORMS Journal on Computing 8(1): 29-40 (1996)

Monika Rauch Henzinger, David P. Williamson: On the Number of Small Cuts in a Graph. Inf. Process. Lett. 59(1): 41-44 (1996)

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson: Gadgets, Approximation, and Linear Programming (extended abstract). FOCS 1996: 617-626

Michel X. Goemans, David P. Williamson: Primal-Dual Approximation Algorithms for Feedback Problems. IPCO 1996: 147-161

Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson: Adversarial Queueing Theory. STOC 1996: 376-385

Alok Aggarwal, Jon M. Kleinberg, David P. Williamson: Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. STOC 1996: 585-594

Sanjeev Khanna, Madhu Sudan, David P. Williamson: A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. Electronic Colloquium on Computational Complexity (ECCC) 3(62) (1996)

David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani: A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. Combinatorica 15(3): 435-454 (1995)

Michel X. Goemans, David P. Williamson: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42(6): 1115-1145 (1995)

Michel X. Goemans, David P. Williamson: A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput. 24(2): 296-317 (1995)

David B. Shmoys, Joel Wein, David P. Williamson: Scheduling Parallel Machines On-Line. SIAM J. Comput. 24(6): 1313-1331 (1995)

Michel X. Goemans, David P. Williamson: New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem. SIAM J. Discrete Math. 7(4): 656-666 (1994)

Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, David P. Williamson: Improved Approximation Algorithms for Network Design Problems. SODA 1994: 223-232

David P. Williamson, Michel X. Goemans: Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. SODA 1994: 355-364

Michel X. Goemans, David P. Williamson: .879-approximation algorithms for MAX CUT and MAX 2SAT. STOC 1994: 422-431

Daniel Bienstock, Michel X. Goemans, David Simchi-Levi, David P. Williamson: A note on the prize collecting traveling salesman problem. Math. Program. 59: 413-420 (1993)

Harold N. Gabow, Michel X. Goemans, David P. Williamson: An efficient approximation algorithm for the survivable network design problem. IPCO 1993: 57-74

Michel X. Goemans, David P. Williamson: A new \frac34-approximation algorithm for MAX SAT. IPCO 1993: 313-321

David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani: A primal-dual approximation algorithm for generalized Steiner network problems. STOC 1993: 708-717

Michel X. Goemans, David P. Williamson: A General Approximation Technique for Constrained Forest Problems. SODA 1992: 307-316

David B. Shmoys, Joel Wein, David P. Williamson: Scheduling Parallel Machines On-Line. FOCS 1991: 131-140

David B. Shmoys, David P. Williamson: Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application. Inf. Process. Lett. 35(6): 281-285 (1990)