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