| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Frans Schalekamp, David P. Williamson, Anke van Zuylen |
A proof of the Boyd-Carr conjecture.  |
SODA  |
2012 |
DBLP BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin Skutella, David P. Williamson |
A note on the generalized min-sum set cover problem. |
Oper. Res. Lett. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen |
On the Integrality Gap of the Subtour LP for the 1,2-TSP |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Frans Schalekamp, David P. Williamson, Anke van Zuylen |
A Proof of the Boyd-Carr Conjecture |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Martin Skutella, David P. Williamson |
A note on the generalized min-sum set cover problem |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Jiawei Qian, David P. Williamson |
An O(logn)-Competitive Algorithm for Online Constrained Forest Problems. |
ICALP |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandrashekhar Nagarajan, David P. Williamson |
An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms. |
SEA |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Anke van Zuylen, Frans Schalekamp, David P. Williamson |
Popular Ranking. |
CTW |
2011 |
DBLP BibTeX RDF |
|
| 1 | Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson |
A General Approach for Incremental Approximation and Hierarchical Clustering. |
SIAM J. Comput. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson |
Approximating the smallest k-edge connected spanning subgraph by LP-rounding. |
Networks |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Yogeshwer Sharma, David P. Williamson |
Stackelberg thresholds in network routing games or the value of altruism. |
Games and Economic Behavior |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Anke van Zuylen, David P. Williamson |
Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems. |
Math. Oper. Res. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Mateo Restrepo, David P. Williamson |
A simple GAP-canceling algorithm for the generalized maximum flow problem. |
Math. Program. |
2009 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000) 68Q25, 05C85, 90C35, 90B10 |
| 1 | Aaron Archer, Asaf Levin, David P. Williamson |
A Faster, Better Approximation Algorithm for the Minimum Latency Problem. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandrashekhar Nagarajan, David P. Williamson |
Offline and Online Facility Leasing. |
IPCO |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandrashekhar Nagarajan, Yogeshwer Sharma, David P. Williamson |
Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements. |
WAOA |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | David P. Williamson, Anke van Zuylen |
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. |
Oper. Res. Lett. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson |
Approximation algorithms for prize collecting forest problems with submodular penalty functions. |
SODA |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Anke van Zuylen, Rajneesh Hegde, Kamal Jain, David P. Williamson |
Deterministic pivoting algorithms for constrained ranking and clustering problems. |
SODA |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Matteo Fischetti, David P. Williamson (eds.) |
Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings |
IPCO |
2007 |
DBLP BibTeX RDF |
|
| 1 | Anke van Zuylen, David P. Williamson |
Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems. |
WAOA |
2007 |
DBLP DOI BibTeX RDF |
feedback arc set in tournaments, derandomization, rank aggregation |
| 1 | Yogeshwer Sharma, David P. Williamson |
Stackelberg thresholds in network routing games or the value of altruism. |
ACM Conference on Electronic Commerce |
2007 |
DBLP DOI BibTeX RDF |
Stackelberg equilibrium, Stackelberg threshold, altruistic flow, centrally controlled flow, game theory, Nash equilibrium, price of anarchy |
| 1 | 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. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Lisa Fleischer, Kamal Jain, David P. Williamson |
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. |
J. Comput. Syst. Sci. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson |
A general approach for incremental approximation and hierarchical clustering. |
SODA |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Mateo Restrepo, David P. Williamson |
A simple GAP-canceling algorithm for the generalized maximum flow problem. |
SODA |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Paat Rusmevichientong, David P. Williamson |
An adaptive algorithm for selecting profitable keywords for search-based advertising services. |
ACM Conference on Electronic Commerce |
2006 |
DBLP DOI BibTeX RDF |
search-based advertising, adaptive algorithms, online optimization, multi-armed bandits |
| 1 | Fabián A. Chudak, David P. Williamson |
Improved approximation algorithms for capacitated facility location problems. |
Math. Program. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson |
Approximating the smallest k-edge connected spanning subgraph by LP-rounding. |
SODA |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. |
J. Comput. Syst. Sci. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Archer, David P. Williamson |
Faster approximation algorithms for the minimum latency problem. |
SODA |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronald Fagin, Ravi Kumar, Kevin S. McCurley, Jasmine Novak, D. Sivakumar, John A. Tomlin, David P. Williamson |
Searching the workplace web. |
WWW |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | R. Ravi, David P. Williamson |
Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. |
Algorithmica |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Takao Asano, David P. Williamson |
Improved Approximation Algorithms for MAX SAT. |
J. Algorithms |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | R. Ravi, David P. Williamson |
Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems. |
SODA |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson |
Adversarial queuing theory. |
J. ACM |
2001 |
DBLP DOI BibTeX RDF |
stability, packet routing, scheduling protocols |
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Lisa Fleischer, Kamal Jain, David P. Williamson |
An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem. |
FOCS |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. |
STOC |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, Joel Wein, David P. Williamson |
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. |
Oper. Res. Lett. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. |
SIAM J. Discrete Math. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson |
The Approximability of Constraint Satisfaction Problems. |
SIAM J. Comput. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson |
Gadgets, Approximation, and Linear Programming. |
SIAM J. Comput. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Takao Asano, David P. Williamson |
Improved approximation algorithms for MAX SAT. |
SODA |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. |
SODA |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Fabián A. Chudak, David P. Williamson |
Improved Approximation Algorithms for Capacitated Facility Location Problems. |
IPCO |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs. |
Combinatorica |
1998 |
DBLP DOI BibTeX RDF |
AMS Subject Classification (1991) Classes: 90C27, 68Q25, 05C85 |
| 1 | Harold N. Gabow, Michel X. Goemans, David P. Williamson |
An efficient approximation algorithm for the survivable network design problem. |
Math. Program. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | R. Ravi, David P. Williamson |
An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. |
Algorithmica |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | David P. Williamson |
Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture). |
WG |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Khanna, Madhu Sudan, David P. Williamson |
A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. |
STOC |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Monika Rauch Henzinger, David P. Williamson |
On the Number of Small Cuts in a Graph. |
Inf. Process. Lett. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | 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) |
1996 |
DBLP BibTeX RDF |
|
| 1 | David P. Williamson, Michel X. Goemans |
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. |
INFORMS Journal on Computing |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
Primal-Dual Approximation Algorithms for Feedback Problems. |
IPCO |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson |
Gadgets, Approximation, and Linear Programming (extended abstract). |
FOCS |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Alok Aggarwal, Jon M. Kleinberg, David P. Williamson |
Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. |
STOC |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson |
Adversarial Queueing Theory. |
STOC |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. |
J. ACM |
1995 |
DBLP DOI BibTeX RDF |
Approximation algorithms, randomized algorithms, satisfiability, convex optimization |
| 1 | David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani |
A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. |
Combinatorica |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | David B. Shmoys, Joel Wein, David P. Williamson |
Scheduling Parallel Machines On-Line. |
SIAM J. Comput. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
A General Approximation Technique for Constrained Forest Problems. |
SIAM J. Comput. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem. |
SIAM J. Discrete Math. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | David P. Williamson, Michel X. Goemans |
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. |
SODA |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
.879-approximation algorithms for MAX CUT and MAX 2SAT. |
STOC |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Bienstock, Michel X. Goemans, David Simchi-Levi, David P. Williamson |
A note on the prize collecting traveling salesman problem. |
Math. Program. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
A new \frac34-approximation algorithm for MAX SAT. |
IPCO |
1993 |
DBLP BibTeX RDF |
|
| 1 | Harold N. Gabow, Michel X. Goemans, David P. Williamson |
An efficient approximation algorithm for the survivable network design problem. |
IPCO |
1993 |
DBLP BibTeX RDF |
|
| 1 | David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani |
A primal-dual approximation algorithm for generalized Steiner network problems. |
STOC |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, David P. Williamson |
A General Approximation Technique for Constrained Forest Problems. |
SODA |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | David B. Shmoys, Joel Wein, David P. Williamson |
Scheduling Parallel Machines On-Line |
FOCS |
1991 |
DBLP DOI BibTeX RDF |
information-theoretic lower bounds, algorithmic techniques, parallel machines, polynomial-time algorithms, online scheduling |
| 1 | David B. Shmoys, David P. Williamson |
Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application. |
Inf. Process. Lett. |
1990 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")