×

Williamson, David P.

Compute Distance To:
Author ID: williamson.david-p Recent zbMATH articles by "Williamson, David P."
Published as: Williamson, David P.; Williamson, D. P.; Williamson, David
Homepage: http://www.davidpwilliamson.net/work/
External Links: MGP · Wikidata · Google Scholar · dblp · GND · IdRef
Documents Indexed: 112 Publications since 1990, including 2 Books
3 Contributions as Editor
Biographic References: 1 Publication
Co-Authors: 73 Co-Authors with 111 Joint Publications
2,146 Co-Co-Authors

Publications by Year

Citations contained in zbMATH Open

90 Publications have been cited 1,927 times in 1,569 Documents Cited by Year
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Zbl 0885.68088
Goemans, Michel X.; Williamson, David P.
584
1995
The design of approximation algorithms. Zbl 1219.90004
Williamson, David P.; Shmoys, David B.
166
2011
A general approximation technique for constrained forest problems. Zbl 0834.68055
Goemans, Michel X.; Williamson, David P.
154
1995
A note on the prize collecting traveling salesman problem. Zbl 0793.90089
Bienstock, Daniel; Goemans, Michel X.; Simchi-Levi, David; Williamson, David
66
1993
Short shop schedules. Zbl 0890.90112
Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast’janov, S. V.; Shmoys, D. B.
64
1997
Improved approximation algorithms for network design problems. Zbl 0873.68005
Goemans, M. X.; Goldberg, A. V.; Plotkin, S.; Shmoys, D. B.; Tardos, É.; Williamson, D. P.
56
1994
Scheduling parallel machines on-line. Zbl 0845.68042
Shmoys, David B.; Wein, Joel; Williamson, David P.
44
1995
The approximability of constraint satisfaction problems. Zbl 0992.68059
Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P.
43
2001
New \(3\over4\)-approximation algorithms for the maximum satisfiability problem. Zbl 0812.90129
Goemans, Michel X.; Williamson, David P.
41
1994
Adversarial queuing theory. Zbl 1320.68053
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
37
2001
Gadgets, approximation, and linear programming. Zbl 0957.68048
Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P.
36
2000
Analyzing the Held-Karp TSP bound: A monotonicity property with application. Zbl 0698.68050
Shmoys, David B.; Williamson, David P.
33
1990
.878-approximation algorithms for MAX CUT and MAX 2SAT. Zbl 1345.68274
Goemans, Michel X.; Williamson, David P.
31
1994
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Zbl 0920.90137
Chudak, Fabián A.; Goemans, Michel X.; Hochbaum, Dorit S.; Williamson, David P.
30
1998
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Zbl 1103.68139
Fleischer, Lisa; Jain, Kamal; Williamson, David P.
30
2006
Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1216.68343
Van Zuylen, Anke; Williamson, David P.
28
2009
Permutation vs. non-permutation flow shop schedules. Zbl 0742.90045
Potts, Chris N.; Shmoys, David B.; Williamson, David P.
23
1991
A general approximation technique for constrained forest problems. Zbl 0818.90124
Goemans, Michel X.; Williamson, David P.
23
1992
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Zbl 1093.90038
Goemans, Michel X.; Williamson, David P.
22
2004
A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 0838.90133
Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V.
21
1995
Improved approximation algorithms for capacitated facility location problems. Zbl 1079.90075
Chudak, Fabián A.; Williamson, David P.
21
2005
Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation. Zbl 1116.90104
Chudak, Fabián A.; Roughgarden, Tim; Williamson, David P.
15
2004
Deterministic algorithms for rank aggregation and other ranking and clustering problems. Zbl 1130.68342
van Zuylen, Anke; Williamson, David P.
15
2008
A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. Zbl 0962.68068
Khanna, Sanjeev; Sudan, Madhu; Williamson, David P.
13
1999
An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 0873.68076
Ravi, R.; Williamson, D. P.
13
1997
A faster, better approximation algorithm for the minimum latency problem. Zbl 1181.68326
Archer, Aaron; Levin, Asaf; Williamson, David P.
12
2008
Improved approximation algorithms for capacitated facility location problems. Zbl 0955.90068
Chudak, Fabián A.; Williamson, David P.
12
1999
Primal-dual approximation algorithms for feedback problems in planar graphs. Zbl 0928.90094
Goemans, Michel X.; Williamson, David P.
11
1998
Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding. Zbl 1205.05125
Gabow, Harold N.; Goemans, Michel X.; Tardos, Éva; Williamson, David P.
11
2009
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Zbl 1176.90079
Williamson, David P.; van Zuylen, Anke
10
2007
Greedy algorithms for the maximum satisfiability problem: simple algorithms and inapproximability bounds. Zbl 1372.68305
Poloczek, Matthias; Schnitger, Georg; Williamson, David P.; van Zuylen, Anke
10
2017
Approximation algorithms for prize collecting forest problems with submodular penalty functions. Zbl 1302.90238
Sharma, Yogeshwer; Swamy, Chaitanya; Williamson, David P.
10
2007
Two-dimensional Gantt charts and a scheduling algorithm of Lawler. Zbl 1054.90032
Goemans, Michel X.; Williamson, David P.
9
2000
A general approach for incremental approximation and hierarchical clustering. Zbl 1209.68648
Lin, Guolong; Nagarajan, Chandrashekhar; Rajaraman, Rajmohan; Williamson, David P.
9
2010
A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 1310.90116
Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V.
9
1993
Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1302.68326
van Zuylen, Anke; Hegde, Rajneesh; Jain, Kamal; Williamson, David P.
9
2007
The primal-dual method for approximation algorithms. Zbl 1030.90111
Williamson, David P.
9
2002
2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture. Zbl 1291.90132
Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke
9
2014
Offline and online facility leasing. Zbl 06958408
Nagarajan, Chandrashekhar; Williamson, David P.
9
2013
Faster approximation algorithms for the minimum latency problem. Zbl 1094.68699
Archer, Aaron; Williamson, David P.
8
2003
An efficient approximation algorithm for the survivable network design problem. Zbl 0923.90136
Gabow, Harold N.; Goemans, Michel X.; Williamson, David P.
8
1993
An efficient approximation algorithm for the survivable network design problem. Zbl 0922.90140
Gabow, Harold N.; Goemans, Michel X.; Williamson, David P.
8
1998
Node-disjoint paths on the mesh and a new trade-off in VLSI layout. Zbl 0947.68113
Aggarwal, Alok; Kleinberg, Jon; Williamson, David P.
7
2000
Approximating minimum-cost graph problems with spanning tree edges. Zbl 0823.90125
Goemans, Michel X.; Williamson, David P.
7
1994
Scheduling parallel machines on-line. Zbl 0800.68214
Shmoys, David B.; Wein, Joel; Williamson, David P.
7
1992
Improved approximation algorithms for MAX SAT. Zbl 0990.68078
Asano, Takao; Williamson, David P.
7
2002
A 1. 47-approximation for a preemptive single-machine scheduling problem. Zbl 0955.90025
Goemans, Michel X.; Wein, Joel M.; Williamson, David P.
6
2000
A general approach for incremental approximation and hierarchical clustering. Zbl 1192.68978
Lin, Guolong; Nagarajan, Chandrashekhar; Rajaraman Rajmohan; Williamson, David P.
6
2006
Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 1017.68157
Ravi, R.; Williamson, D. P.
6
2002
Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Zbl 1456.90137
Paul, Alice; Freund, Daniel; Ferber, Aaron; Shmoys, David B.; Williamson, David P.
5
2020
The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem. Zbl 1402.90114
Gutekunst, Samuel C.; Williamson, David P.
5
2018
Improved approximation algorithms for MAX SAT. Zbl 0952.90019
Asano, Takao; Williamson, David P.
5
2000
Stackelberg thresholds in network routing games or the value of altruism. Zbl 1168.91332
Sharma, Yogeshwer; Williamson, David P.
5
2009
A new \(\frac{3}{4}\)-approximation algorithm for \(\text{MAX SAT}\). Zbl 0929.90071
Goemans, Michel X.; Williamson, David P.
5
1993
An experimental evaluation of the best-of-many Christofides’ algorithm for the traveling salesman problem. Zbl 1369.90144
Genova, Kyle; Williamson, David P.
5
2015
Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation. Zbl 0987.68102
Chudak, Fabián A.; Roughgarden, Tim; Williamson, David P.
5
2001
Network flow algorithms. Zbl 1426.90003
Williamson, David P.
4
2019
Adversarial queueing theory. Zbl 0934.60079
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
4
1996
A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 0934.68110
Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P.
4
1999
Offline and online facility leasing. Zbl 1143.90355
Nagarajan, Chandrashekhar; Williamson, David P.
4
2008
On the integrality gap of the subtour LP for the \(1,2\)-TSP. Zbl 1354.90114
Qian, Jiawei; Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke
4
2012
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Zbl 1323.90047
Goemans, Michel X.; Williamson, David
4
2001
An \(O(\log n)\)-competitive algorithm for online constrained forest problems. Zbl 1332.68296
Qian, Jiawei; Williamson, David P.
3
2011
Pricing problems under the nested logit model with a quality consistency constraint. Zbl 1414.91141
Davis, James M.; Topaloglu, Huseyin; Williamson, David P.
3
2017
On some recent approximation algorithms for MAX SAT. Zbl 1407.68553
Poloczek, Matthias; Williamson, David P.; van Zuylen, Anke
3
2014
Popular ranking. Zbl 1358.91051
van Zuylen, Anke; Schalekamp, Frans; Williamson, David P.
3
2014
A note on the generalized min-sum set cover problem. Zbl 1235.90131
Skutella, Martin; Williamson, David P.
3
2011
Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding. Zbl 1297.05130
Gabow, Harold N.; Goemans, Michel X.; Tardos, Éva; Williamson, David P.
3
2005
Assortment optimization over time. Zbl 1408.90304
Davis, James M.; Topaloglu, Huseyin; Williamson, David P.
3
2015
An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 0848.05046
Ravi, R.; Williamson, David P.
2
1995
A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 1122.90351
Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P.
2
2002
Analysis of the Held-Karp lower bound for the asymmetric TSP. Zbl 0768.90079
Williamson, David P.
2
1992
A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem. Zbl 1355.68290
San Felice, Mário César; Williamson, David P.; Lee, Orlando
2
2016
On the integrality gap of the subtour LP for the 1,2-TSP. Zbl 1309.90049
Qian, Jiawei; Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke
2
2015
Primal-dual approximation algorithms for feedback problems in planar graphs. Zbl 1415.90101
Goemans, Michel X.; Williamson, David P.
2
1996
Online constrained forest and prize-collecting network design. Zbl 1412.68302
Qian, Jiawei; Umboh, Seeun William; Williamson, David P.
2
2018
Prize-collecting TSP with a budget constraint. Zbl 1442.90170
Paul, Alice; Freund, Daniel; Ferber, Aaron; Shmoys, David B.; Williamson, David P.
2
2017
Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem. Zbl 1434.90169
Gutekunst, Samuel C.; Williamson, David P.
1
2019
An experimental evaluation of fast approximation algorithms for the maximum satisfiability problem. Zbl 1414.68105
Poloczek, Matthias; Williamson, David P.
1
2017
Computational experience with an approximation algorithm on large-scale Euclidean matching instances. Zbl 0855.90074
Williamson, David P.; Goemans, Michel X.
1
1996
Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 1093.68672
Ravi, R.; Williamson, David P.
1
2002
A dual-fitting \(\frac{3}{2}\)-approximation algorithm for some minimum-cost graph problems. Zbl 1365.68467
Davis, James M.; Williamson, David P.
1
2012
A simple GAP-canceling algorithm for the generalized maximum flow problem. Zbl 1169.90319
Restrepo, Mateo; Williamson, David P.
1
2009
Integer programming and combinatorial optimization. 12th international IPCO conference, Ithaca, NY, USA, June 25–27, 2007. Proceedings. Zbl 1121.90003
1
2007
Maximizing a submodular function with viability constraints. Zbl 1394.68439
Dvořák, Wolfgang; Henzinger, Monika; Williamson, David P.
1
2013
An experimental evaluation of the best-of-many Christofides’ algorithm for the traveling salesman problem. Zbl 1372.90090
Genova, Kyle; Williamson, David P.
1
2017
The online connected facility location problem. Zbl 1352.68286
San Felice, Mário César; Williamson, David P.; Lee, Orlando
1
2014
On the number of small cut in a graph. Zbl 1046.68630
Henzinger, Monika; Williamson, David P.
1
1996
On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems. Zbl 1146.90032
Uma, R. N.; Wein, Joel; Williamson, David P.
1
2006
Greedy algorithms for the single-demand facility location problem. Zbl 1409.90102
Cheung, Sin-Shuen; Williamson, David P.
1
2017
Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Zbl 1456.90137
Paul, Alice; Freund, Daniel; Ferber, Aaron; Shmoys, David B.; Williamson, David P.
5
2020
Network flow algorithms. Zbl 1426.90003
Williamson, David P.
4
2019
Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem. Zbl 1434.90169
Gutekunst, Samuel C.; Williamson, David P.
1
2019
The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem. Zbl 1402.90114
Gutekunst, Samuel C.; Williamson, David P.
5
2018
Online constrained forest and prize-collecting network design. Zbl 1412.68302
Qian, Jiawei; Umboh, Seeun William; Williamson, David P.
2
2018
Greedy algorithms for the maximum satisfiability problem: simple algorithms and inapproximability bounds. Zbl 1372.68305
Poloczek, Matthias; Schnitger, Georg; Williamson, David P.; van Zuylen, Anke
10
2017
Pricing problems under the nested logit model with a quality consistency constraint. Zbl 1414.91141
Davis, James M.; Topaloglu, Huseyin; Williamson, David P.
3
2017
Prize-collecting TSP with a budget constraint. Zbl 1442.90170
Paul, Alice; Freund, Daniel; Ferber, Aaron; Shmoys, David B.; Williamson, David P.
2
2017
An experimental evaluation of fast approximation algorithms for the maximum satisfiability problem. Zbl 1414.68105
Poloczek, Matthias; Williamson, David P.
1
2017
An experimental evaluation of the best-of-many Christofides’ algorithm for the traveling salesman problem. Zbl 1372.90090
Genova, Kyle; Williamson, David P.
1
2017
Greedy algorithms for the single-demand facility location problem. Zbl 1409.90102
Cheung, Sin-Shuen; Williamson, David P.
1
2017
A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem. Zbl 1355.68290
San Felice, Mário César; Williamson, David P.; Lee, Orlando
2
2016
An experimental evaluation of the best-of-many Christofides’ algorithm for the traveling salesman problem. Zbl 1369.90144
Genova, Kyle; Williamson, David P.
5
2015
Assortment optimization over time. Zbl 1408.90304
Davis, James M.; Topaloglu, Huseyin; Williamson, David P.
3
2015
On the integrality gap of the subtour LP for the 1,2-TSP. Zbl 1309.90049
Qian, Jiawei; Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke
2
2015
2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture. Zbl 1291.90132
Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke
9
2014
On some recent approximation algorithms for MAX SAT. Zbl 1407.68553
Poloczek, Matthias; Williamson, David P.; van Zuylen, Anke
3
2014
Popular ranking. Zbl 1358.91051
van Zuylen, Anke; Schalekamp, Frans; Williamson, David P.
3
2014
The online connected facility location problem. Zbl 1352.68286
San Felice, Mário César; Williamson, David P.; Lee, Orlando
1
2014
Offline and online facility leasing. Zbl 06958408
Nagarajan, Chandrashekhar; Williamson, David P.
9
2013
Maximizing a submodular function with viability constraints. Zbl 1394.68439
Dvořák, Wolfgang; Henzinger, Monika; Williamson, David P.
1
2013
On the integrality gap of the subtour LP for the \(1,2\)-TSP. Zbl 1354.90114
Qian, Jiawei; Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke
4
2012
A dual-fitting \(\frac{3}{2}\)-approximation algorithm for some minimum-cost graph problems. Zbl 1365.68467
Davis, James M.; Williamson, David P.
1
2012
The design of approximation algorithms. Zbl 1219.90004
Williamson, David P.; Shmoys, David B.
166
2011
An \(O(\log n)\)-competitive algorithm for online constrained forest problems. Zbl 1332.68296
Qian, Jiawei; Williamson, David P.
3
2011
A note on the generalized min-sum set cover problem. Zbl 1235.90131
Skutella, Martin; Williamson, David P.
3
2011
A general approach for incremental approximation and hierarchical clustering. Zbl 1209.68648
Lin, Guolong; Nagarajan, Chandrashekhar; Rajaraman, Rajmohan; Williamson, David P.
9
2010
Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1216.68343
Van Zuylen, Anke; Williamson, David P.
28
2009
Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding. Zbl 1205.05125
Gabow, Harold N.; Goemans, Michel X.; Tardos, Éva; Williamson, David P.
11
2009
Stackelberg thresholds in network routing games or the value of altruism. Zbl 1168.91332
Sharma, Yogeshwer; Williamson, David P.
5
2009
A simple GAP-canceling algorithm for the generalized maximum flow problem. Zbl 1169.90319
Restrepo, Mateo; Williamson, David P.
1
2009
Deterministic algorithms for rank aggregation and other ranking and clustering problems. Zbl 1130.68342
van Zuylen, Anke; Williamson, David P.
15
2008
A faster, better approximation algorithm for the minimum latency problem. Zbl 1181.68326
Archer, Aaron; Levin, Asaf; Williamson, David P.
12
2008
Offline and online facility leasing. Zbl 1143.90355
Nagarajan, Chandrashekhar; Williamson, David P.
4
2008
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Zbl 1176.90079
Williamson, David P.; van Zuylen, Anke
10
2007
Approximation algorithms for prize collecting forest problems with submodular penalty functions. Zbl 1302.90238
Sharma, Yogeshwer; Swamy, Chaitanya; Williamson, David P.
10
2007
Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1302.68326
van Zuylen, Anke; Hegde, Rajneesh; Jain, Kamal; Williamson, David P.
9
2007
Integer programming and combinatorial optimization. 12th international IPCO conference, Ithaca, NY, USA, June 25–27, 2007. Proceedings. Zbl 1121.90003
1
2007
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Zbl 1103.68139
Fleischer, Lisa; Jain, Kamal; Williamson, David P.
30
2006
A general approach for incremental approximation and hierarchical clustering. Zbl 1192.68978
Lin, Guolong; Nagarajan, Chandrashekhar; Rajaraman Rajmohan; Williamson, David P.
6
2006
On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems. Zbl 1146.90032
Uma, R. N.; Wein, Joel; Williamson, David P.
1
2006
Improved approximation algorithms for capacitated facility location problems. Zbl 1079.90075
Chudak, Fabián A.; Williamson, David P.
21
2005
Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding. Zbl 1297.05130
Gabow, Harold N.; Goemans, Michel X.; Tardos, Éva; Williamson, David P.
3
2005
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Zbl 1093.90038
Goemans, Michel X.; Williamson, David P.
22
2004
Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation. Zbl 1116.90104
Chudak, Fabián A.; Roughgarden, Tim; Williamson, David P.
15
2004
Faster approximation algorithms for the minimum latency problem. Zbl 1094.68699
Archer, Aaron; Williamson, David P.
8
2003
The primal-dual method for approximation algorithms. Zbl 1030.90111
Williamson, David P.
9
2002
Improved approximation algorithms for MAX SAT. Zbl 0990.68078
Asano, Takao; Williamson, David P.
7
2002
Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 1017.68157
Ravi, R.; Williamson, D. P.
6
2002
A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 1122.90351
Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P.
2
2002
Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 1093.68672
Ravi, R.; Williamson, David P.
1
2002
The approximability of constraint satisfaction problems. Zbl 0992.68059
Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P.
43
2001
Adversarial queuing theory. Zbl 1320.68053
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
37
2001
Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation. Zbl 0987.68102
Chudak, Fabián A.; Roughgarden, Tim; Williamson, David P.
5
2001
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Zbl 1323.90047
Goemans, Michel X.; Williamson, David
4
2001
Gadgets, approximation, and linear programming. Zbl 0957.68048
Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P.
36
2000
Two-dimensional Gantt charts and a scheduling algorithm of Lawler. Zbl 1054.90032
Goemans, Michel X.; Williamson, David P.
9
2000
Node-disjoint paths on the mesh and a new trade-off in VLSI layout. Zbl 0947.68113
Aggarwal, Alok; Kleinberg, Jon; Williamson, David P.
7
2000
A 1. 47-approximation for a preemptive single-machine scheduling problem. Zbl 0955.90025
Goemans, Michel X.; Wein, Joel M.; Williamson, David P.
6
2000
Improved approximation algorithms for MAX SAT. Zbl 0952.90019
Asano, Takao; Williamson, David P.
5
2000
A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. Zbl 0962.68068
Khanna, Sanjeev; Sudan, Madhu; Williamson, David P.
13
1999
Improved approximation algorithms for capacitated facility location problems. Zbl 0955.90068
Chudak, Fabián A.; Williamson, David P.
12
1999
A primal-dual schema based approximation algorithm for the element connectivity problem. Zbl 0934.68110
Jain, Kamal; Măndoiu, Ion; Vazirani, Vijay V.; Williamson, David P.
4
1999
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Zbl 0920.90137
Chudak, Fabián A.; Goemans, Michel X.; Hochbaum, Dorit S.; Williamson, David P.
30
1998
Primal-dual approximation algorithms for feedback problems in planar graphs. Zbl 0928.90094
Goemans, Michel X.; Williamson, David P.
11
1998
An efficient approximation algorithm for the survivable network design problem. Zbl 0922.90140
Gabow, Harold N.; Goemans, Michel X.; Williamson, David P.
8
1998
Short shop schedules. Zbl 0890.90112
Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast’janov, S. V.; Shmoys, D. B.
64
1997
An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 0873.68076
Ravi, R.; Williamson, D. P.
13
1997
Adversarial queueing theory. Zbl 0934.60079
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
4
1996
Primal-dual approximation algorithms for feedback problems in planar graphs. Zbl 1415.90101
Goemans, Michel X.; Williamson, David P.
2
1996
Computational experience with an approximation algorithm on large-scale Euclidean matching instances. Zbl 0855.90074
Williamson, David P.; Goemans, Michel X.
1
1996
On the number of small cut in a graph. Zbl 1046.68630
Henzinger, Monika; Williamson, David P.
1
1996
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Zbl 0885.68088
Goemans, Michel X.; Williamson, David P.
584
1995
A general approximation technique for constrained forest problems. Zbl 0834.68055
Goemans, Michel X.; Williamson, David P.
154
1995
Scheduling parallel machines on-line. Zbl 0845.68042
Shmoys, David B.; Wein, Joel; Williamson, David P.
44
1995
A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 0838.90133
Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V.
21
1995
An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 0848.05046
Ravi, R.; Williamson, David P.
2
1995
Improved approximation algorithms for network design problems. Zbl 0873.68005
Goemans, M. X.; Goldberg, A. V.; Plotkin, S.; Shmoys, D. B.; Tardos, É.; Williamson, D. P.
56
1994
New \(3\over4\)-approximation algorithms for the maximum satisfiability problem. Zbl 0812.90129
Goemans, Michel X.; Williamson, David P.
41
1994
.878-approximation algorithms for MAX CUT and MAX 2SAT. Zbl 1345.68274
Goemans, Michel X.; Williamson, David P.
31
1994
Approximating minimum-cost graph problems with spanning tree edges. Zbl 0823.90125
Goemans, Michel X.; Williamson, David P.
7
1994
A note on the prize collecting traveling salesman problem. Zbl 0793.90089
Bienstock, Daniel; Goemans, Michel X.; Simchi-Levi, David; Williamson, David
66
1993
A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 1310.90116
Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V.
9
1993
An efficient approximation algorithm for the survivable network design problem. Zbl 0923.90136
Gabow, Harold N.; Goemans, Michel X.; Williamson, David P.
8
1993
A new \(\frac{3}{4}\)-approximation algorithm for \(\text{MAX SAT}\). Zbl 0929.90071
Goemans, Michel X.; Williamson, David P.
5
1993
A general approximation technique for constrained forest problems. Zbl 0818.90124
Goemans, Michel X.; Williamson, David P.
23
1992
Scheduling parallel machines on-line. Zbl 0800.68214
Shmoys, David B.; Wein, Joel; Williamson, David P.
7
1992
Analysis of the Held-Karp lower bound for the asymmetric TSP. Zbl 0768.90079
Williamson, David P.
2
1992
Permutation vs. non-permutation flow shop schedules. Zbl 0742.90045
Potts, Chris N.; Shmoys, David B.; Williamson, David P.
23
1991
Analyzing the Held-Karp TSP bound: A monotonicity property with application. Zbl 0698.68050
Shmoys, David B.; Williamson, David P.
33
1990
all top 5

Cited by 2,451 Authors

38 Williamson, David P.
29 Xu, Dachuan
24 Nutov, Zeev
20 Du, Donglei
18 Wu, Chenchen
16 Ravi, Ramamoorthi
14 Woeginger, Gerhard Johannes
13 Anjos, Miguel F.
13 Nagarajan, Viswanath
12 Escoffier, Bruno
12 Kortsarz, Guy
12 Levin, Asaf
12 Niedermeier, Rolf
11 Goemans, Michel X.
11 Lisser, Abdel
10 Bampis, Evripidis
10 Maffioli, Francesco
10 Mastrolilli, Monaldo
10 Shmoys, David B.
9 Ben-Ameur, Walid
9 Fiorini, Samuel
9 Pardalos, Panos M.
9 Pokutta, Sebastian
9 Rendl, Franz
9 Sitters, Rene A.
9 Svensson, Ola
9 Wang, Zhenbo
9 Xia, Yong
8 Bertsimas, Dimitris John
8 Chekuri, Chandra S.
8 Chen, Jian-er
8 Epstein, Leah
8 Hajiaghayi, Mohammad Taghi
8 Lin, Guohui
8 Sviridenko, Maxim I.
8 Swamy, Chaitanya
8 van Zuylen, Anke
8 Xu, Chengxian
8 Zhang, Shuzhong
7 Feige, Uriel
7 Jonsson, Peter A.
7 Kowalski, Dariusz R.
7 Lee, Jon
7 Li, Duan
7 Neto, José
7 Resende, Mauricio G. C.
7 Singer, Amit
7 Vazirani, Vijay V.
7 Xu, Fengmin
7 Ye, Yinyu
7 Yu, Xingxing
7 Živný, Stanislav
6 Bandeira, Afonso S.
6 Braun, Gábor
6 Buchbinder, Niv
6 Chen, Bo
6 Chen, Xujin
6 Chlebus, Bogdan Stanislaw
6 Fukunaga, Takuro
6 Gupta, Anupam
6 Jansen, Klaus
6 Kononov, Alexander V.
6 Krokhin, Andrei A.
6 Kurpisz, Adam
6 Laurent, Monique
6 Letchford, Adam N.
6 Ling, Aifan
6 Ljubić, Ivana
6 Lu, Cheng
6 Malick, Jérôme
6 Paul, Alice
6 Schwartz, Roy
6 Segev, Danny
6 Sevastyanov, Sergeĭ Vasil’evich
6 Stougie, Leen
6 Strusevich, Vitaly A.
6 Trevisan, Luca
6 van Ee, Martijn
6 Zhang, Jiawei
5 Bazgan, Cristina
5 Blesa, Maria J.
5 Boyd, Sylvia C.
5 Burer, Samuel
5 Chakrabarty, Deeparnab
5 de Klerk, Etienne
5 Fampa, Marcia Helena C.
5 Guo, Jiong
5 Gutekunst, Samuel C.
5 Haouari, Mohamed
5 Hassin, Refael
5 He, Simai
5 Hüffner, Falk
5 Kawarabayashi, Ken-ichi
5 Kim, Sunyoung
5 Kobayashi, Yusuke
5 Komusiewicz, Christian
5 Könemann, Jochen
5 Laekhanukit, Bundit
5 Levi, Retsef
5 Marathe, Madhav V.
...and 2,351 more Authors
all top 5

Cited in 194 Serials

109 Theoretical Computer Science
108 Mathematical Programming. Series A. Series B
83 Discrete Applied Mathematics
81 Algorithmica
62 European Journal of Operational Research
57 Operations Research Letters
47 Journal of Combinatorial Optimization
42 Information Processing Letters
37 Journal of Global Optimization
34 Computers & Operations Research
29 SIAM Journal on Computing
28 Theory of Computing Systems
27 Journal of Scheduling
26 Journal of Computer and System Sciences
25 Discrete Optimization
23 SIAM Journal on Optimization
22 SIAM Journal on Discrete Mathematics
20 Computational Optimization and Applications
19 Annals of Operations Research
19 Optimization Methods & Software
18 Networks
16 INFORMS Journal on Computing
15 Optimization Letters
14 Operations Research
12 Mathematics of Operations Research
11 Journal of Combinatorial Theory. Series B
10 Journal of the Operations Research Society of China
9 Cybernetics and Systems Analysis
9 RAIRO. Operations Research
8 Applied Mathematics and Computation
8 Linear Algebra and its Applications
7 Artificial Intelligence
7 Journal of Computational and Applied Mathematics
7 Journal of Optimization Theory and Applications
7 Combinatorica
7 Optimization
7 Journal of Discrete Algorithms
7 Journal of Industrial and Management Optimization
6 Information and Computation
6 Asia-Pacific Journal of Operational Research
6 Random Structures & Algorithms
6 Annals of Mathematics and Artificial Intelligence
6 Journal of Machine Learning Research (JMLR)
5 Machine Learning
5 Bulletin of the American Mathematical Society. New Series
5 International Transactions in Operational Research
5 Foundations of Computational Mathematics
5 Mathematical Programming Computation
4 Discrete Mathematics
4 The Annals of Statistics
4 Automatica
4 Information Sciences
4 Acta Mathematicae Applicatae Sinica. English Series
4 International Journal of Foundations of Computer Science
4 Games and Economic Behavior
4 Mathematical Problems in Engineering
4 Journal of the ACM
4 Science China. Mathematics
3 Israel Journal of Mathematics
3 Discrete & Computational Geometry
3 Journal of Scientific Computing
3 Numerical Algorithms
3 Distributed Computing
3 Computational Complexity
3 SIAM Journal on Scientific Computing
3 Applied Mathematics. Series B (English Edition)
3 Applied and Computational Harmonic Analysis
3 Combinatorics, Probability and Computing
3 International Journal of Computer Vision
3 Top
3 ACM Journal of Experimental Algorithmics
3 Algorithms
3 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
3 Theory of Computing
3 Numerical Algebra, Control and Optimization
3 Computer Science Review
3 SIAM Journal on Mathematics of Data Science
2 Communications on Pure and Applied Mathematics
2 Journal of Mathematical Analysis and Applications
2 Journal of Economic Theory
2 Journal of Pure and Applied Algebra
2 Opsearch
2 European Journal of Combinatorics
2 Journal of Information & Optimization Sciences
2 Systems & Control Letters
2 Mathematical Social Sciences
2 Physica D
2 Graphs and Combinatorics
2 Journal of Cryptology
2 Neural Computation
2 Japan Journal of Industrial and Applied Mathematics
2 The Annals of Applied Probability
2 Discrete Event Dynamic Systems
2 Applied Mathematical Modelling
2 Proceedings of the National Academy of Sciences of the United States of America
2 The Electronic Journal of Combinatorics
2 Advances in Computational Mathematics
2 The Journal of Artificial Intelligence Research (JAIR)
2 Discussiones Mathematicae. Graph Theory
2 The Journal of Fourier Analysis and Applications
...and 94 more Serials
all top 5

Cited in 46 Fields

1,041 Operations research, mathematical programming (90-XX)
751 Computer science (68-XX)
320 Combinatorics (05-XX)
72 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
47 Numerical analysis (65-XX)
33 Statistics (62-XX)
24 Probability theory and stochastic processes (60-XX)
22 Linear and multilinear algebra; matrix theory (15-XX)
19 Information and communication theory, circuits (94-XX)
15 Convex and discrete geometry (52-XX)
13 Calculus of variations and optimal control; optimization (49-XX)
11 Biology and other natural sciences (92-XX)
11 Systems theory; control (93-XX)
10 Functional analysis (46-XX)
9 Algebraic geometry (14-XX)
8 Quantum theory (81-XX)
7 Mathematical logic and foundations (03-XX)
7 Statistical mechanics, structure of matter (82-XX)
5 Order, lattices, ordered algebraic structures (06-XX)
4 General algebraic systems (08-XX)
4 Optics, electromagnetic theory (78-XX)
3 General and overarching topics; collections (00-XX)
3 Number theory (11-XX)
3 Geometry (51-XX)
2 Commutative algebra (13-XX)
2 Group theory and generalizations (20-XX)
2 Real functions (26-XX)
2 Partial differential equations (35-XX)
2 Dynamical systems and ergodic theory (37-XX)
1 History and biography (01-XX)
1 Field theory and polynomials (12-XX)
1 Nonassociative rings and algebras (17-XX)
1 Measure and integration (28-XX)
1 Functions of a complex variable (30-XX)
1 Several complex variables and analytic spaces (32-XX)
1 Special functions (33-XX)
1 Ordinary differential equations (34-XX)
1 Approximations and expansions (41-XX)
1 Harmonic analysis on Euclidean spaces (42-XX)
1 Abstract harmonic analysis (43-XX)
1 Operator theory (47-XX)
1 Differential geometry (53-XX)
1 Manifolds and cell complexes (57-XX)
1 Global analysis, analysis on manifolds (58-XX)
1 Mechanics of deformable solids (74-XX)
1 Mathematics education (97-XX)

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.