×

zbMATH — the first resource for mathematics

Williamson, David P.

Compute Distance To:
Author ID: williamson.david-p Recent zbMATH articles by "Williamson, David P."
Published as: Williamson, D. P.; Williamson, David; Williamson, David P.
Homepage: http://www.davidpwilliamson.net/work/home
External Links: MGP · Wikidata · dblp · GND
Documents Indexed: 108 Publications since 1990, including 4 Books

Publications by Year

Citations contained in zbMATH Open

86 Publications have been cited 1,691 times in 1,378 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.
516
1995
The design of approximation algorithms. Zbl 1219.90004
Williamson, David P.; Shmoys, David B.
133
2011
A general approximation technique for constrained forest problems. Zbl 0834.68055
Goemans, Michel X.; Williamson, David P.
133
1995
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.
58
1997
A note on the prize collecting traveling salesman problem. Zbl 0793.90089
Bienstock, Daniel; Goemans, Michel X.; Simchi-Levi, David; Williamson, David
53
1993
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.
50
1994
Scheduling parallel machines on-line. Zbl 0845.68042
Shmoys, David B.; Wein, Joel; Williamson, David P.
40
1995
New \(3\over4\)-approximation algorithms for the maximum satisfiability problem. Zbl 0812.90129
Goemans, Michel X.; Williamson, David P.
37
1994
Gadgets, approximation, and linear programming. Zbl 0957.68048
Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P.
35
2000
Adversarial queuing theory. Zbl 1320.68053
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
34
2001
The approximability of constraint satisfaction problems. Zbl 0992.68059
Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P.
34
2001
.878-approximation algorithms for MAX CUT and MAX 2SAT. Zbl 1345.68274
Goemans, Michel X.; Williamson, David P.
29
1994
Analyzing the Held-Karp TSP bound: A monotonicity property with application. Zbl 0698.68050
Shmoys, David B.; Williamson, David P.
29
1990
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Zbl 1103.68139
Fleischer, Lisa; Jain, Kamal; Williamson, David P.
28
2006
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.
28
1998
A general approximation technique for constrained forest problems. Zbl 0818.90124
Goemans, Michel X.; Williamson, David P.
23
1992
Permutation vs. non-permutation flow shop schedules. Zbl 0742.90045
Potts, Chris N.; Shmoys, David B.; Williamson, David P.
23
1991
Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1216.68343
Van Zuylen, Anke; Williamson, David P.
22
2009
Improved approximation algorithms for capacitated facility location problems. Zbl 1079.90075
Chudak, Fabián A.; Williamson, David P.
19
2005
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Zbl 1093.90038
Goemans, Michel X.; Williamson, David P.
19
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.
19
1995
Deterministic algorithms for rank aggregation and other ranking and clustering problems. Zbl 1130.68342
van Zuylen, Anke; Williamson, David P.
14
2008
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.
14
2004
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.
12
1997
Improved approximation algorithms for capacitated facility location problems. Zbl 0955.90068
Chudak, Fabián A.; Williamson, David P.
11
1999
Primal-dual approximation algorithms for feedback problems in planar graphs. Zbl 0928.90094
Goemans, Michel X.; Williamson, David P.
11
1998
Scheduling parallel machines on-line. Zbl 0800.68214
Shmoys, David B.; Wein, Joel; Williamson, David P.
10
1992
A faster, better approximation algorithm for the minimum latency problem. Zbl 1181.68326
Archer, Aaron; Levin, Asaf; Williamson, David P.
9
2008
Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1302.68326
van Zuylen, Anke; Hegde, Rajneesh; Jain, Kamal; Williamson, David P.
9
2007
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Zbl 1176.90079
Williamson, David P.; van Zuylen, Anke
9
2007
The primal-dual method for approximation algorithms. Zbl 1030.90111
Williamson, David P.
9
2002
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
A general approach for incremental approximation and hierarchical clustering. Zbl 1209.68648
Lin, Guolong; Nagarajan, Chandrashekhar; Rajaraman, Rajmohan; Williamson, David P.
8
2010
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.
8
2009
Faster approximation algorithms for the minimum latency problem. Zbl 1094.68699
Archer, Aaron; Williamson, David P.
8
2003
Two-dimensional Gantt charts and a scheduling algorithm of Lawler. Zbl 1054.90032
Goemans, Michel X.; Williamson, David P.
8
2000
Adversarial queueing theory. Zbl 0934.60079
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
8
1996
An efficient approximation algorithm for the survivable network design problem. Zbl 0923.90136
Gabow, Harold N.; Goemans, Michel X.; Williamson, David P.
8
1993
Approximation algorithms for prize collecting forest problems with submodular penalty functions. Zbl 1302.90238
Sharma, Yogeshwer; Swamy, Chaitanya; Williamson, David P.
7
2007
Improved approximation algorithms for MAX SAT. Zbl 0990.68078
Asano, Takao; Williamson, David P.
7
2002
An efficient approximation algorithm for the survivable network design problem. Zbl 0922.90140
Gabow, Harold N.; Goemans, Michel X.; Williamson, David P.
7
1998
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
6
2014
A general approach for incremental approximation and hierarchical clustering. Zbl 1192.68978
Lin, Guolong; Nagarajan, Chandrashekhar; Rajaraman Rajmohan; Williamson, David P.
6
2006
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
Node-disjoint paths on the mesh and a new trade-off in VLSI layout. Zbl 0947.68113
Aggarwal, Alok; Kleinberg, Jon; Williamson, David P.
6
2000
Approximating minimum-cost graph problems with spanning tree edges. Zbl 0823.90125
Goemans, Michel X.; Williamson, David P.
6
1994
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
5
2017
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
Offline and online facility leasing. Zbl 1143.90355
Nagarajan, Chandrashekhar; Williamson, David P.
5
2008
Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 1017.68157
Ravi, R.; Williamson, D. P.
5
2002
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Zbl 1323.90047
Goemans, Michel X.; Williamson, David
5
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
Improved approximation algorithms for MAX SAT. Zbl 0952.90019
Asano, Takao; Williamson, David P.
5
2000
A new \(\frac{3}{4}\)-approximation algorithm for \(\text{MAX SAT}\). Zbl 0929.90071
Goemans, Michel X.; Williamson, David P.
5
1993
The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem. Zbl 1402.90114
Gutekunst, Samuel C.; Williamson, David P.
4
2018
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
Stackelberg thresholds in network routing games or the value of altruism. Zbl 1168.91332
Sharma, Yogeshwer; Williamson, David P.
4
2009
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
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
Offline and online facility leasing. Zbl 06958408
Nagarajan, Chandrashekhar; Williamson, David P.
3
2013
A note on the generalized min-sum set cover problem. Zbl 1235.90131
Skutella, Martin; Williamson, David P.
3
2011
An \(O(\log n)\)-competitive algorithm for online constrained forest problems. Zbl 1332.68296
Qian, Jiawei; 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.
2
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
Popular ranking. Zbl 1358.91051
van Zuylen, Anke; Schalekamp, Frans; Williamson, David P.
2
2014
On some recent approximation algorithms for MAX SAT. Zbl 1407.68553
Poloczek, Matthias; Williamson, David P.; van Zuylen, Anke
2
2014
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
Primal-dual approximation algorithms for feedback problems in planar graphs. Zbl 1415.90101
Goemans, Michel X.; Williamson, David P.
2
1996
An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 0848.05046
Ravi, R.; Williamson, David P.
2
1995
Network flow algorithms. Zbl 1426.90003
Williamson, David P.
1
2019
Online constrained forest and prize-collecting network design. Zbl 1412.68302
Qian, Jiawei; Umboh, Seeun William; Williamson, David P.
1
2018
Greedy algorithms for the single-demand facility location problem. Zbl 1409.90102
Cheung, Sin-Shuen; Williamson, David P.
1
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
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
1
2016
The online connected facility location problem. Zbl 1352.68286
San Felice, Mário César; Williamson, David P.; Lee, Orlando
1
2014
Maximizing a submodular function with viability constraints. Zbl 1394.68439
Dvořák, Wolfgang; Henzinger, Monika; Williamson, David P.
1
2013
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
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
Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 1093.68672
Ravi, R.; Williamson, David P.
1
2002
On the number of small cut in a graph. Zbl 1046.68630
Henzinger, Monika; Williamson, David P.
1
1996
Computational experience with an approximation algorithm on large-scale Euclidean matching instances. Zbl 0855.90074
Williamson, David P.; Goemans, Michel X.
1
1996
Analysis of the Held-Karp lower bound for the asymmetric TSP. Zbl 0768.90079
Williamson, David P.
1
1992
Network flow algorithms. Zbl 1426.90003
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.
4
2018
Online constrained forest and prize-collecting network design. Zbl 1412.68302
Qian, Jiawei; Umboh, Seeun William; Williamson, David P.
1
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
5
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
Greedy algorithms for the single-demand facility location problem. Zbl 1409.90102
Cheung, Sin-Shuen; Williamson, David P.
1
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
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
1
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.
2
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
6
2014
Popular ranking. Zbl 1358.91051
van Zuylen, Anke; Schalekamp, Frans; Williamson, David P.
2
2014
On some recent approximation algorithms for MAX SAT. Zbl 1407.68553
Poloczek, Matthias; Williamson, David P.; van Zuylen, Anke
2
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.
3
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.
133
2011
A note on the generalized min-sum set cover problem. Zbl 1235.90131
Skutella, Martin; Williamson, David P.
3
2011
An \(O(\log n)\)-competitive algorithm for online constrained forest problems. Zbl 1332.68296
Qian, Jiawei; 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.
8
2010
Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1216.68343
Van Zuylen, Anke; Williamson, David P.
22
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.
8
2009
Stackelberg thresholds in network routing games or the value of altruism. Zbl 1168.91332
Sharma, Yogeshwer; Williamson, David P.
4
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.
14
2008
A faster, better approximation algorithm for the minimum latency problem. Zbl 1181.68326
Archer, Aaron; Levin, Asaf; Williamson, David P.
9
2008
Offline and online facility leasing. Zbl 1143.90355
Nagarajan, Chandrashekhar; Williamson, David P.
5
2008
Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1302.68326
van Zuylen, Anke; Hegde, Rajneesh; Jain, Kamal; Williamson, David P.
9
2007
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Zbl 1176.90079
Williamson, David P.; van Zuylen, Anke
9
2007
Approximation algorithms for prize collecting forest problems with submodular penalty functions. Zbl 1302.90238
Sharma, Yogeshwer; Swamy, Chaitanya; Williamson, David P.
7
2007
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Zbl 1103.68139
Fleischer, Lisa; Jain, Kamal; Williamson, David P.
28
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.
19
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.
19
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.
14
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.
5
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
Adversarial queuing theory. Zbl 1320.68053
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
34
2001
The approximability of constraint satisfaction problems. Zbl 0992.68059
Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P.
34
2001
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Zbl 1323.90047
Goemans, Michel X.; Williamson, David
5
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
Gadgets, approximation, and linear programming. Zbl 0957.68048
Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P.
35
2000
Two-dimensional Gantt charts and a scheduling algorithm of Lawler. Zbl 1054.90032
Goemans, Michel X.; Williamson, David P.
8
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
Node-disjoint paths on the mesh and a new trade-off in VLSI layout. Zbl 0947.68113
Aggarwal, Alok; Kleinberg, Jon; 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.
11
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.
28
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.
7
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.
58
1997
An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 0873.68076
Ravi, R.; Williamson, D. P.
12
1997
Adversarial queueing theory. Zbl 0934.60079
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
8
1996
Primal-dual approximation algorithms for feedback problems in planar graphs. Zbl 1415.90101
Goemans, Michel X.; Williamson, David P.
2
1996
On the number of small cut in a graph. Zbl 1046.68630
Henzinger, Monika; Williamson, David P.
1
1996
Computational experience with an approximation algorithm on large-scale Euclidean matching instances. Zbl 0855.90074
Williamson, David P.; Goemans, Michel X.
1
1996
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Zbl 0885.68088
Goemans, Michel X.; Williamson, David P.
516
1995
A general approximation technique for constrained forest problems. Zbl 0834.68055
Goemans, Michel X.; Williamson, David P.
133
1995
Scheduling parallel machines on-line. Zbl 0845.68042
Shmoys, David B.; Wein, Joel; Williamson, David P.
40
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.
19
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.
50
1994
New \(3\over4\)-approximation algorithms for the maximum satisfiability problem. Zbl 0812.90129
Goemans, Michel X.; Williamson, David P.
37
1994
.878-approximation algorithms for MAX CUT and MAX 2SAT. Zbl 1345.68274
Goemans, Michel X.; Williamson, David P.
29
1994
Approximating minimum-cost graph problems with spanning tree edges. Zbl 0823.90125
Goemans, Michel X.; Williamson, David P.
6
1994
A note on the prize collecting traveling salesman problem. Zbl 0793.90089
Bienstock, Daniel; Goemans, Michel X.; Simchi-Levi, David; Williamson, David
53
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.
10
1992
Analysis of the Held-Karp lower bound for the asymmetric TSP. Zbl 0768.90079
Williamson, David P.
1
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.
29
1990
all top 5

Cited by 2,225 Authors

35 Williamson, David P.
26 Xu, Dachuan
22 Nutov, Zeev
16 Du, Donglei
16 Wu, Chenchen
13 Woeginger, Gerhard Johannes
12 Anjos, Miguel F.
12 Kortsarz, Guy
11 Goemans, Michel X.
11 Levin, Asaf
11 Lisser, Abdel
11 Nagarajan, Viswanath
11 Niedermeier, Rolf
10 Maffioli, Francesco
10 Mastrolilli, Monaldo
10 Ravi, Ramamoorthi
10 Rendl, Franz
9 Ben-Ameur, Walid
9 Fiorini, Samuel
9 Pardalos, Panos M.
9 Pokutta, Sebastian
9 Shmoys, David B.
8 Chekuri, Chandra S.
8 Epstein, Leah
8 Hajiaghayi, Mohammad Taghi
8 Sitters, Rene A.
8 Svensson, Ola
8 Sviridenko, Maxim I.
8 van Zuylen, Anke
8 Wang, Zhenbo
8 Xu, Chengxian
8 Zhang, Shuzhong
7 Bertsimas, Dimitris John
7 Chen, Jian-er
7 Feige, Uriel
7 Jansen, Klaus
7 Lin, Guohui
7 Neto, José
7 Resende, Mauricio G. C.
7 Singer, Amit
7 Trevisan, Luca
7 Vazirani, Vijay V.
7 Xia, Yong
7 Xu, Fengmin
7 Ye, Yinyu
6 Braun, Gábor
6 Chen, Bo
6 Chlebus, Bogdan Stanislaw
6 Escoffier, Bruno
6 Hassin, Refael
6 Jonsson, Peter A.
6 Laurent, Monique
6 Lee, Jon
6 Letchford, Adam N.
6 Li, Duan
6 Ling, Aifan
6 Ljubić, Ivana
6 Malick, Jérôme
6 Sevastyanov, Sergeĭ Vasil’evich
6 Strusevich, Vitaly A.
6 van Ee, Martijn
6 Zhang, Jiawei
5 Arkin, Esther M.
5 Bazgan, Cristina
5 Buchbinder, Niv
5 Burer, Samuel
5 Chakrabarty, Deeparnab
5 Chen, Xujin
5 de Klerk, Etienne
5 Fukunaga, Takuro
5 Guo, Jiong
5 Haouari, Mohamed
5 He, Simai
5 Hüffner, Falk
5 Kobayashi, Yusuke
5 Komusiewicz, Christian
5 Krokhin, Andrei A.
5 Levi, Retsef
5 Lu, Cheng
5 Marathe, Madhav V.
5 Marchetti-Spaccamela, Alberto
5 Mömke, Tobias
5 Paschos, Vangelis Th.
5 Penn, Michal
5 Saurabh, Saket
5 Segev, Danny
5 Serna, Maria José
5 Stougie, Leen
5 Swamy, Chaitanya
5 Thapper, Johan
5 Tu, Jianhua
5 Vempala, Santosh S.
5 Wiese, Andreas
5 Xing, Wenxun
5 Yu, Xingxing
5 Živný, Stanislav
4 Adasme, Pablo
4 Anantharamu, Lakshmi
4 Angel, Eric
4 Bampis, Evripidis
...and 2,125 more Authors
all top 5

Cited in 175 Serials

106 Theoretical Computer Science
104 Mathematical Programming. Series A. Series B
82 Discrete Applied Mathematics
75 Algorithmica
60 European Journal of Operational Research
57 Operations Research Letters
41 Journal of Combinatorial Optimization
38 Information Processing Letters
35 Journal of Global Optimization
29 Computers & Operations Research
26 Theory of Computing Systems
25 Journal of Computer and System Sciences
25 SIAM Journal on Computing
25 Journal of Scheduling
20 Discrete Optimization
19 SIAM Journal on Discrete Mathematics
18 Networks
18 Annals of Operations Research
17 Computational Optimization and Applications
17 Optimization Methods & Software
15 SIAM Journal on Optimization
13 Optimization Letters
11 Journal of Combinatorial Theory. Series B
10 Operations Research
9 Journal of Computational and Applied Mathematics
9 Mathematics of Operations Research
9 Linear Algebra and its Applications
9 Cybernetics and Systems Analysis
9 RAIRO. Operations Research
8 Applied Mathematics and Computation
7 Artificial Intelligence
7 Journal of Optimization Theory and Applications
7 Information and Computation
7 Journal of Discrete Algorithms
7 Journal of the Operations Research Society of China
6 Combinatorica
6 Optimization
6 Random Structures & Algorithms
6 Journal of Industrial and Management Optimization
5 Asia-Pacific Journal of Operational Research
5 Bulletin of the American Mathematical Society. New Series
5 International Transactions in Operational Research
5 Journal of Machine Learning Research (JMLR)
4 Discrete Mathematics
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 Annals of Mathematics and Artificial Intelligence
4 Mathematical Problems in Engineering
4 Journal of the ACM
4 Mathematical Programming Computation
4 Science China. Mathematics
3 Israel Journal of Mathematics
3 The Annals of Statistics
3 Discrete & Computational Geometry
3 Distributed Computing
3 Computational Complexity
3 SIAM Journal on Scientific Computing
3 Applied and Computational Harmonic Analysis
3 Combinatorics, Probability and Computing
3 International Journal of Computer Vision
3 Top
3 INFORMS Journal on Computing
3 Foundations of Computational Mathematics
3 Algorithms
3 Theory of Computing
3 Numerical Algebra, Control and Optimization
2 Communications on Pure and Applied Mathematics
2 Journal of Mathematical Analysis and Applications
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 Journal of Cryptology
2 Machine Learning
2 Neural Computation
2 Japan Journal of Industrial and Applied Mathematics
2 The Annals of Applied Probability
2 Discrete Event Dynamic Systems
2 Numerical Algorithms
2 Applied Mathematical Modelling
2 Proceedings of the National Academy of Sciences of the United States of America
2 Applied Mathematics. Series B (English Edition)
2 The Journal of Artificial Intelligence Research (JAIR)
2 The Journal of Fourier Analysis and Applications
2 Journal of Heuristics
2 CEJOR. Central European Journal of Operations Research
2 Journal of Systems Science and Complexity
2 4OR
2 Computational Management Science
2 SIAM Journal on Imaging Sciences
2 Discrete Mathematics, Algorithms and Applications
2 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
2 Computer Science Review
2 ACM Transactions on Computation Theory
1 Computer Methods in Applied Mechanics and Engineering
...and 75 more Serials
all top 5

Cited in 43 Fields

925 Operations research, mathematical programming (90-XX)
654 Computer science (68-XX)
279 Combinatorics (05-XX)
62 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
40 Numerical analysis (65-XX)
26 Statistics (62-XX)
21 Probability theory and stochastic processes (60-XX)
19 Linear and multilinear algebra; matrix theory (15-XX)
16 Information and communication theory, circuits (94-XX)
14 Convex and discrete geometry (52-XX)
11 Systems theory; control (93-XX)
10 Calculus of variations and optimal control; optimization (49-XX)
9 Functional analysis (46-XX)
8 Quantum theory (81-XX)
8 Biology and other natural sciences (92-XX)
7 Algebraic geometry (14-XX)
6 Mathematical logic and foundations (03-XX)
4 Order, lattices, ordered algebraic structures (06-XX)
4 Statistical mechanics, structure of matter (82-XX)
3 General and overarching topics; collections (00-XX)
3 General algebraic systems (08-XX)
3 Number theory (11-XX)
3 Optics, electromagnetic theory (78-XX)
2 Commutative algebra (13-XX)
2 Group theory and generalizations (20-XX)
2 Real functions (26-XX)
2 Dynamical systems and ergodic theory (37-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 Partial differential equations (35-XX)
1 Approximations and expansions (41-XX)
1 Harmonic analysis on Euclidean spaces (42-XX)
1 Operator theory (47-XX)
1 Geometry (51-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

Wikidata Timeline

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