David P. Williamson

	2009
66		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)
	2008
65		Chandrashekhar Nagarajan, David P. Williamson: Offline and Online Facility Leasing. IPCO 2008: 303-315
64		Chandrashekhar Nagarajan, Yogeshwer Sharma, David P. Williamson: Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements. WAOA 2008: 174-187
63		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)
	2007
62		Matteo Fischetti, David P. Williamson: Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings Springer 2007
61		Yogeshwer Sharma, David P. Williamson: Stackelberg thresholds in network routing games or the value of altruism. ACM Conference on Electronic Commerce 2007: 93-102
60		Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson: Approximation algorithms for prize collecting forest problems with submodular penalty functions. SODA 2007: 1275-1284
59		Anke van Zuylen, Rajneesh Hegde, Kamal Jain, David P. Williamson: Deterministic pivoting algorithms for constrained ranking and clustering problems. SODA 2007: 405-414
58		Anke van Zuylen, David P. Williamson: Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems. WAOA 2007: 260-273
57		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)
	2006
56		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
55		Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson: A general approach for incremental approximation and hierarchical clustering. SODA 2006: 1147-1156
54		Mateo Restrepo, David P. Williamson: A simple GAP-canceling algorithm for the generalized maximum flow problem. SODA 2006: 534-543
53		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)
52		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)
	2005
51		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
50		Fabián A. Chudak, David P. Williamson: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102(2): 207-222 (2005)
	2004
49		Michel X. Goemans, David P. Williamson: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. J. Comput. Syst. Sci. 68(2): 442-470 (2004)
48		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)
	2003
47		Aaron Archer, David P. Williamson: Faster approximation algorithms for the minimum latency problem. SODA 2003: 88-96
46		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
	2002
45		R. Ravi, David P. Williamson: Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems. SODA 2002: 1000-1001
44		R. Ravi, David P. Williamson: Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. Algorithmica 34(1): 98-107 (2002)
43		Takao Asano, David P. Williamson: Improved Approximation Algorithms for MAX SAT. J. Algorithms 42(1): 173-202 (2002)
42		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)
	2001
41		Lisa Fleischer, Kamal Jain, David P. Williamson: An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem. FOCS 2001: 339-347
40		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
39		Michel X. Goemans, David P. Williamson: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. STOC 2001: 443-452
38		Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson: Adversarial queuing theory. J. ACM 48(1): 13-38 (2001)
	2000
37		Takao Asano, David P. Williamson: Improved approximation algorithms for MAX SAT. SODA 2000: 96-105
36		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)
35		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)
34		Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson: Gadgets, Approximation, and Linear Programming. SIAM J. Comput. 29(6): 2074-2097 (2000)
33		Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson: The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. 30(6): 1863-1920 (2000)
32		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)
	1999
31		Fabián A. Chudak, David P. Williamson: Improved Approximation Algorithms for Capacitated Facility Location Problems. IPCO 1999: 99-113
30		Michel X. Goemans, David P. Williamson: Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SODA 1999: 366-375
29		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
	1998
28		Michel X. Goemans, David P. Williamson: Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs. Combinatorica 18(1): 37-59 (1998)
27		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)
26		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)
	1997
25		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
24		David P. Williamson: Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture). WG 1997: 1
23		R. Ravi, David P. Williamson: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. Algorithmica 18(1): 21-43 (1997)
	1996
22		Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson: Gadgets, Approximation, and Linear Programming (extended abstract). FOCS 1996: 617-626
21		Michel X. Goemans, David P. Williamson: Primal-Dual Approximation Algorithms for Feedback Problems. IPCO 1996: 147-161
20		Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson: Adversarial Queueing Theory. STOC 1996: 376-385
19		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
18		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)
17		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)
16		Monika Rauch Henzinger, David P. Williamson: On the Number of Small Cuts in a Graph. Inf. Process. Lett. 59(1): 41-44 (1996)
	1995
15		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)
14		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)
13		Michel X. Goemans, David P. Williamson: A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput. 24(2): 296-317 (1995)
12		David B. Shmoys, Joel Wein, David P. Williamson: Scheduling Parallel Machines On-Line. SIAM J. Comput. 24(6): 1313-1331 (1995)
	1994
11		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
10		David P. Williamson, Michel X. Goemans: Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. SODA 1994: 355-364
9		Michel X. Goemans, David P. Williamson: .879-approximation algorithms for MAX CUT and MAX 2SAT. STOC 1994: 422-431
8		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)
	1993
7		Michel X. Goemans, David P. Williamson: A new \frac34-approximation algorithm for MAX SAT. IPCO 1993: 313-321
6		Harold N. Gabow, Michel X. Goemans, David P. Williamson: An efficient approximation algorithm for the survivable network design problem. IPCO 1993: 57-74
5		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
4		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)
	1992
3		Michel X. Goemans, David P. Williamson: A General Approximation Technique for Constrained Forest Problems. SODA 1992: 307-316
	1991
2		David B. Shmoys, Joel Wein, David P. Williamson: Scheduling Parallel Machines On-Line FOCS 1991: 131-140
	1990
1		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)

Coauthor Index

1	Alok Aggarwal	[19] [35]
2	Aaron Archer	[47] [63]
3	Takao Asano	[37] [43]
4	Daniel Bienstock	[4]
5	Allan Borodin	[20] [38]
6	Fabián A. Chudak	[26] [31] [40] [48] [50]
7	Ronald Fagin	[46]
8	Matteo Fischetti	[62]
9	Lisa Fleischer	[41] [53]
10	Harold N. Gabow	[6] [27] [51] [66]
11	Michel X. Goemans	[3] [4] [5] [6] [7] [8] [9] [10] [11] [13] [14] [15] [17] [21] [26] [27] [28] [30] [32] [36] [39] [49] [51] [66]
12	Andrew V. Goldberg	[11]
13	Rajneesh Hegde	[59]
14	Monika Rauch Henzinger (Monika Rauch)	[16]
15	Dorit S. Hochbaum	[26]
16	Kamal Jain	[29] [41] [42] [53] [59]
17	Sanjeev Khanna	[18] [25] [33]
18	Jon M. Kleinberg	[19] [20] [35] [38]
19	Ravi Kumar (S. Ravi Kumar)	[46]
20	Asaf Levin	[63]
21	Guolong Lin	[55]
22	Ion I. Mandoiu	[29] [42]
23	Kevin S. McCurley	[46]
24	Milena Mihail	[5] [15]
25	Chandrashekhar Nagarajan	[55] [64] [65]
26	Jasmine Novak	[46]
27	Serge A. Plotkin	[11]
28	Prabhakar Raghavan	[20] [38]
29	Rajmohan Rajaraman	[55]
30	R. Ravi	[23] [44] [45]
31	Mateo Restrepo	[54]
32	Tim Roughgarden	[40] [48]
33	Paat Rusmevichientong	[56]
34	Yogeshwer Sharma	[60] [61] [64]
35	David B. Shmoys	[1] [2] [11] [12]
36	David Simchi-Levi	[4]
37	D. Sivakumar	[46]
38	Gregory B. Sorkin	[22] [34]
39	Madhu Sudan	[18] [20] [22] [25] [33] [34] [38]
40	Chaitanya Swamy	[60]
41	Éva Tardos	[11] [51] [66]
42	John A. Tomlin	[46]
43	Luca Trevisan	[22] [33] [34]
44	R. N. Uma	[52]
45	Vijay V. Vazirani	[5] [15] [29] [42]
46	Joel Wein	[2] [12] [36] [52]
47	Anke van Zuylen	[57] [58] [59]

Colors in the list of coauthors