Edit Profile (opens in new tab) Williamson, David P. Co-Author Distance Author ID: williamson.david-p Published as: Williamson, David P.; Williamson, D. P.; Williamson, David more...less Homepage: http://www.davidpwilliamson.net/work/ External Links: MGP · Wikidata · Google Scholar · dblp · GND · IdRef Documents Indexed: 124 Publications since 1990, including 2 Books and 1 Additional arXiv Preprint 4 Contributions as Editor Biographic References: 1 Publication Co-Authors: 79 Co-Authors with 123 Joint Publications 2,576 Co-Co-Authors all top 5 Co-Authors 5 single-authored 25 Goemans, Michel Xavier 11 Shmoys, David B. 11 van Zuylen, Anke 6 Gutekunst, Samuel C. 6 Jin, Billy 6 Nagarajan, Chandrashekhar 6 Paul, Alice 5 Chudak, Fabián A. 5 Mirka, Renee 5 Poloczek, Matthias 5 Rauch Henzinger, Monika 5 Schalekamp, Frans 5 Sudan, Madhu 4 Davis, James M. 4 Freund, Daniel 4 Gabow, Harold N. 4 Jain, Kamal C. 4 Kleinberg, Jon Michael 4 Qian, Jiawei 4 Ravi, Ramamoorthi 4 Vazirani, Vijay V. 4 Wein, Joel M. 3 Ferber, Aaron 3 Lee, Orlando 3 San Felice, Mário César 3 Sharma, Yogeshwer 3 Tardos, Éva 3 Umboh, Seeun William 2 Aggarwal, Alok 2 Archer, Aaron F. 2 Asano, Takao 2 Borodin, Allan B. 2 Cheung, Sin-Shuen 2 Dvořák, Wolfgang 2 Genova, Kyle 2 Khanna, Sanjeev 2 Klein, Nathan 2 Lin, Guolong 2 Măndoiu, Ion I. 2 Mihail, Milena 2 Naor, Joseph Seffi 2 Peng, Richard 2 Raghavan, Prabhakar 2 Rajaraman, Rajmohan 2 Restrepo, Mateo 2 Roughgarden, Tim 2 Singh, Mohit 2 Smedira, Devin 2 Topaloglu, Huseyin 2 Trevisan, Luca 1 Bienstock, Daniel 1 Breen, Emmett 1 Couëtoux, Basile 1 Dey, Santanu Subhas 1 Fischetti, Matteo 1 Fleischer, Lisa K. 1 Goldberg, Andrew V. 1 Hall, Leslie A. 1 Hegde, Rajneesh 1 Hochbaum, Dorit S. 1 Hoogeveen, Johannes Adzer 1 Hurkens, Cor A. J. 1 Jansen, Klaus 1 Karger, David R. 1 Lenstra, Jan Karel 1 Levin, Asaf 1 Plotkin, Serge A. 1 Potts, Chris N. 1 Rolim, José D. P. 1 Schnitger, Georg 1 Schulz, Andreas S. 1 Sevastyanov, Sergeĭ Vasil’evich 1 Simchi-Levi, David 1 Skutella, Martin 1 Sorkin, Gregory B. 1 Swamy, Chaitanya 1 Uma, R. N. 1 Vempala, Santosh S. 1 Wang, Zichen all top 5 Serials 12 Operations Research Letters 10 Mathematical Programming. Series A. Series B 9 Algorithmica 8 SIAM Journal on Computing 6 Mathematics of Operations Research 3 SIAM Journal on Discrete Mathematics 3 ACM Journal of Experimental Algorithmics 2 Discrete Applied Mathematics 2 Information Processing Letters 2 Journal of Computer and System Sciences 2 Journal of Algorithms 2 Combinatorica 2 INFORMS Journal on Computing 2 Lecture Notes in Computer Science 1 Journal of the Association for Computing Machinery 1 Networks 1 Operations Research 1 Theoretical Computer Science 1 Games and Economic Behavior 1 Proceedings of the National Academy of Sciences of the United States of America 1 SIAM Journal on Optimization 1 Journal of the ACM 1 RIMS Kokyuroku 1 Discrete Optimization 1 LIPIcs – Leibniz International Proceedings in Informatics 1 Environmetrics all top 5 Fields 86 Operations research, mathematical programming (90-XX) 81 Computer science (68-XX) 30 Combinatorics (05-XX) 5 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 4 General and overarching topics; collections (00-XX) 3 Probability theory and stochastic processes (60-XX) 2 Biology and other natural sciences (92-XX) 2 Information and communication theory, circuits (94-XX) 1 Statistics (62-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 101 Publications have been cited 2,735 times in 2,191 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. 785 1995 The design of approximation algorithms. Zbl 1219.90004 Williamson, David P.; Shmoys, David B. 300 2011 A general approximation technique for constrained forest problems. Zbl 0834.68055 Goemans, Michel X.; Williamson, David P. 213 1995 A note on the prize collecting traveling salesman problem. Zbl 0793.90089 Bienstock, Daniel; Goemans, Michel X.; Simchi-Levi, David; Williamson, David 88 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. 88 1994 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. 81 1997 .878-approximation algorithms for MAX CUT and MAX 2SAT. Zbl 1345.68274 Goemans, Michel X.; Williamson, David P. 61 1994 The approximability of constraint satisfaction problems. Zbl 0992.68059 Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P. 60 2001 New \(3\over4\)-approximation algorithms for the maximum satisfiability problem. Zbl 0812.90129 Goemans, Michel X.; Williamson, David P. 54 1994 Gadgets, approximation, and linear programming. Zbl 0957.68048 Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P. 52 2000 Adversarial queuing theory. Zbl 1320.68053 Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P. 52 2001 Scheduling parallel machines on-line. Zbl 0845.68042 Shmoys, David B.; Wein, Joel; Williamson, David P. 47 1995 Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Zbl 1103.68139 Fleischer, Lisa; Jain, Kamal; Williamson, David P. 42 2006 Analyzing the Held-Karp TSP bound: A monotonicity property with application. Zbl 0698.68050 Shmoys, David B.; Williamson, David P. 39 1990 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. 37 1998 A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 0838.90133 Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V. 36 1995 Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1216.68343 Van Zuylen, Anke; Williamson, David P. 35 2009 A general approximation technique for constrained forest problems. Zbl 0818.90124 Goemans, Michel X.; Williamson, David P. 29 1992 Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Zbl 1093.90038 Goemans, Michel X.; Williamson, David P. 29 2004 Improved approximation algorithms for capacitated facility location problems. Zbl 1079.90075 Chudak, Fabián A.; Williamson, David P. 28 2005 Permutation vs. non-permutation flow shop schedules. Zbl 0742.90045 Potts, Chris N.; Shmoys, David B.; Williamson, David P. 26 1991 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. 25 2009 Deterministic algorithms for rank aggregation and other ranking and clustering problems. Zbl 1130.68342 van Zuylen, Anke; Williamson, David P. 25 2008 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 21 2017 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. 19 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. 18 1999 Offline and online facility leasing. Zbl 1506.90141 Nagarajan, Chandrashekhar; Williamson, David P. 17 2013 An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 0873.68076 Ravi, R.; Williamson, D. P. 16 1997 A general approach for incremental approximation and hierarchical clustering. Zbl 1209.68648 Lin, Guolong; Nagarajan, Chandrashekhar; Rajaraman, Rajmohan; Williamson, David P. 16 2010 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 15 2014 Primal-dual approximation algorithms for feedback problems in planar graphs. Zbl 0928.90094 Goemans, Michel X.; Williamson, David P. 15 1998 Network flow algorithms. Zbl 1426.90003 Williamson, David P. 15 2019 A faster, better approximation algorithm for the minimum latency problem. Zbl 1181.68326 Archer, Aaron; Levin, Asaf; Williamson, David P. 14 2008 Improved approximation algorithms for capacitated facility location problems. Zbl 0955.90068 Chudak, Fabián A.; Williamson, David P. 13 1999 Approximation algorithms for prize collecting forest problems with submodular penalty functions. Zbl 1302.90238 Sharma, Yogeshwer; Swamy, Chaitanya; Williamson, David P. 13 2007 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. 12 2020 A primal-dual approximation algorithm for generalized Steiner network problems. Zbl 1310.90116 Williamson, David P.; Goemans, Michel X.; Mihail, Milena; Vazirani, Vijay V. 12 1993 A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Zbl 1176.90079 Williamson, David P.; van Zuylen, Anke 12 2007 Two-dimensional Gantt charts and a scheduling algorithm of Lawler. Zbl 1054.90032 Goemans, Michel X.; Williamson, David P. 11 2000 An efficient approximation algorithm for the survivable network design problem. Zbl 0922.90140 Gabow, Harold N.; Goemans, Michel X.; Williamson, David P. 11 1998 Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1302.68326 van Zuylen, Anke; Hegde, Rajneesh; Jain, Kamal; Williamson, David P. 11 2007 Adversarial queueing theory. Zbl 0934.60079 Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P. 10 1996 Approximating minimum-cost graph problems with spanning tree edges. Zbl 0823.90125 Goemans, Michel X.; Williamson, David P. 10 1994 An efficient approximation algorithm for the survivable network design problem. Zbl 0923.90136 Gabow, Harold N.; Goemans, Michel X.; Williamson, David P. 10 1993 The primal-dual method for approximation algorithms. Zbl 1030.90111 Williamson, David P. 9 2002 Faster approximation algorithms for the minimum latency problem. Zbl 1094.68699 Archer, Aaron; Williamson, David P. 9 2003 Scheduling parallel machines on-line. Zbl 0800.68214 Shmoys, David B.; Wein, Joel; Williamson, David P. 9 1992 Improved approximation algorithms for MAX SAT. Zbl 0990.68078 Asano, Takao; Williamson, David P. 8 2002 Node-disjoint paths on the mesh and a new trade-off in VLSI layout. Zbl 0947.68113 Aggarwal, Alok; Kleinberg, Jon; Williamson, David P. 8 2000 A general approach for incremental approximation and hierarchical clustering. Zbl 1192.68978 Lin, Guolong; Nagarajan, Chandrashekhar; Rajaraman, Rajmohan; Williamson, David P. 8 2006 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. 7 2001 Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 1017.68157 Ravi, R.; Williamson, D. P. 7 2002 Improved approximation algorithms for MAX SAT. Zbl 0952.90019 Asano, Takao; Williamson, David P. 7 2000 Exploratory ensemble designs for environmental models using \(k\)-extended Latin hypercubes. Zbl 1525.62234 Williamson, D. 7 2015 Popular ranking. Zbl 1358.91051 van Zuylen, Anke; Schalekamp, Frans; Williamson, David P. 6 2014 A new \(\frac{3}{4}\)-approximation algorithm for \(\text{MAX SAT}\). Zbl 0929.90071 Goemans, Michel X.; Williamson, David P. 6 1993 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 Offline and online facility leasing. Zbl 1143.90355 Nagarajan, Chandrashekhar; Williamson, David P. 6 2008 Pricing problems under the nested logit model with a quality consistency constraint. Zbl 1414.91141 Davis, James M.; Topaloglu, Huseyin; Williamson, David P. 6 2017 Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Zbl 1323.90047 Goemans, Michel X.; Williamson, David 6 2001 On the number of small cut in a graph. Zbl 1046.68630 Henzinger, Monika; Williamson, David P. 5 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. 5 1999 A note on the generalized min-sum set cover problem. Zbl 1235.90131 Skutella, Martin; Williamson, David P. 5 2011 Stackelberg thresholds in network routing games or the value of altruism. Zbl 1168.91332 Sharma, Yogeshwer; Williamson, David P. 5 2009 The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem. Zbl 1402.90114 Gutekunst, Samuel C.; Williamson, David P. 5 2018 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 An experimental evaluation of the best-of-many Christofides’ algorithm for the traveling salesman problem. Zbl 1372.90090 Genova, Kyle; Williamson, David P. 5 2017 Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model. Zbl 1533.68416 Jin, Billy; Williamson, David P. 5 2022 An \(O(\log n)\)-competitive algorithm for online constrained forest problems. Zbl 1332.68296 Qian, Jiawei; Williamson, David P. 4 2011 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 proof of the Boyd-Carr conjecture. Zbl 1423.90236 Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke 4 2012 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. 3 1995 On some recent approximation algorithms for MAX SAT. Zbl 1407.68553 Poloczek, Matthias; Williamson, David P.; van Zuylen, Anke 3 2014 A simple GAP-canceling algorithm for the generalized maximum flow problem. Zbl 1169.90319 Restrepo, Mateo; Williamson, David P. 3 2009 Online constrained forest and prize-collecting network design. Zbl 1412.68302 Qian, Jiawei; Umboh, Seeun William; Williamson, David P. 3 2018 Prize-collecting TSP with a budget constraint. Zbl 1442.90170 Paul, Alice; Freund, Daniel; Ferber, Aaron; Shmoys, David B.; Williamson, David P. 3 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 3 2016 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. 3 2002 Primal-dual approximation algorithms for feedback problems in planar graphs. Zbl 1415.90101 Goemans, Michel X.; Williamson, David P. 2 1996 Analysis of the Held-Karp lower bound for the asymmetric TSP. Zbl 0768.90079 Williamson, David P. 2 1992 Computational experience with an approximation algorithm on large-scale Euclidean matching instances. Zbl 0855.90074 Williamson, David P.; Goemans, Michel X. 2 1996 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 Node-disjoint paths on the mesh and a new trade-off in VLSI layout. Zbl 0936.68117 Aggarwal, Alok; Kleinberg, Jon; Williamson, David P. 1 1996 The online prize-collecting facility location problem. Zbl 1353.90080 San Felice, Mário César; Cheung, Sin-Shuen; Lee, Orlando; Williamson, David P. 1 2015 Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 1093.68672 Ravi, R.; Williamson, David P. 1 2002 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 online connected facility location problem. Zbl 1352.68286 San Felice, Mário César; Williamson, David P.; Lee, Orlando 1 2014 An experimental evaluation of fast approximation algorithms for the maximum satisfiability problem. Zbl 1414.68105 Poloczek, Matthias; Williamson, David P. 1 2017 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 Greedy algorithms for the single-demand facility location problem. Zbl 1409.90102 Cheung, Sin-Shuen; Williamson, David P. 1 2017 Integer programming and combinatorial optimization. 12th international IPCO conference, Ithaca, NY, USA, June 25–27, 2007. Proceedings. Zbl 1121.90003 1 2007 Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Zbl 1372.68012 1 2017 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 The circlet inequalities: a new, circulant-based, facet-defining inequality for the TSP. Zbl 1540.90237 Gutekunst, Samuel C.; Williamson, David P. 1 2023 Tight bounds for online weighted tree augmentation. Zbl 1522.68415 Naor, Joseph (Seffi); Umboh, Seeun William; Williamson, David P. 1 2019 Recursive random contraction revisited. Zbl 07848175 Karger, David R.; Williamson, David P. 1 2021 Graph coloring and semidefinite rank. Zbl 1497.90143 Mirka, Renee; Smedira, Devin; Williamson, David P. 1 2022 The circlet inequalities: a new, circulant-based, facet-defining inequality for the TSP. Zbl 1540.90237 Gutekunst, Samuel C.; Williamson, David P. 1 2023 Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model. Zbl 1533.68416 Jin, Billy; Williamson, David P. 5 2022 Graph coloring and semidefinite rank. Zbl 1497.90143 Mirka, Renee; Smedira, Devin; Williamson, David P. 1 2022 Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps. Zbl 1492.90146 Gutekunst, Samuel C.; Williamson, David P. 1 2022 Recursive random contraction revisited. Zbl 07848175 Karger, David R.; Williamson, David P. 1 2021 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. 12 2020 Network flow algorithms. Zbl 1426.90003 Williamson, David P. 15 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 Tight bounds for online weighted tree augmentation. Zbl 1522.68415 Naor, Joseph (Seffi); Umboh, Seeun William; 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. 3 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 21 2017 Pricing problems under the nested logit model with a quality consistency constraint. Zbl 1414.91141 Davis, James M.; Topaloglu, Huseyin; Williamson, David P. 6 2017 An experimental evaluation of the best-of-many Christofides’ algorithm for the traveling salesman problem. Zbl 1372.90090 Genova, Kyle; Williamson, David P. 5 2017 Prize-collecting TSP with a budget constraint. Zbl 1442.90170 Paul, Alice; Freund, Daniel; Ferber, Aaron; Shmoys, David B.; Williamson, David P. 3 2017 An experimental evaluation of fast approximation algorithms for the maximum satisfiability problem. Zbl 1414.68105 Poloczek, Matthias; 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 Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Zbl 1372.68012 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 3 2016 Exploratory ensemble designs for environmental models using \(k\)-extended Latin hypercubes. Zbl 1525.62234 Williamson, D. 7 2015 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 The online prize-collecting facility location problem. Zbl 1353.90080 San Felice, Mário César; Cheung, Sin-Shuen; Lee, Orlando; Williamson, David P. 1 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 15 2014 Popular ranking. Zbl 1358.91051 van Zuylen, Anke; Schalekamp, Frans; Williamson, David P. 6 2014 On some recent approximation algorithms for MAX SAT. Zbl 1407.68553 Poloczek, Matthias; Williamson, David P.; van Zuylen, Anke 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 1506.90141 Nagarajan, Chandrashekhar; Williamson, David P. 17 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 proof of the Boyd-Carr conjecture. Zbl 1423.90236 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. 300 2011 A note on the generalized min-sum set cover problem. Zbl 1235.90131 Skutella, Martin; Williamson, David P. 5 2011 An \(O(\log n)\)-competitive algorithm for online constrained forest problems. Zbl 1332.68296 Qian, Jiawei; Williamson, David P. 4 2011 A general approach for incremental approximation and hierarchical clustering. Zbl 1209.68648 Lin, Guolong; Nagarajan, Chandrashekhar; Rajaraman, Rajmohan; Williamson, David P. 16 2010 Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1216.68343 Van Zuylen, Anke; Williamson, David P. 35 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. 25 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. 3 2009 Deterministic algorithms for rank aggregation and other ranking and clustering problems. Zbl 1130.68342 van Zuylen, Anke; Williamson, David P. 25 2008 A faster, better approximation algorithm for the minimum latency problem. Zbl 1181.68326 Archer, Aaron; Levin, Asaf; Williamson, David P. 14 2008 Offline and online facility leasing. Zbl 1143.90355 Nagarajan, Chandrashekhar; Williamson, David P. 6 2008 Approximation algorithms for prize collecting forest problems with submodular penalty functions. Zbl 1302.90238 Sharma, Yogeshwer; Swamy, Chaitanya; Williamson, David P. 13 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 12 2007 Deterministic pivoting algorithms for constrained ranking and clustering problems. Zbl 1302.68326 van Zuylen, Anke; Hegde, Rajneesh; Jain, Kamal; Williamson, David P. 11 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. 42 2006 A general approach for incremental approximation and hierarchical clustering. Zbl 1192.68978 Lin, Guolong; Nagarajan, Chandrashekhar; Rajaraman, Rajmohan; Williamson, David P. 8 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. 28 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. 29 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. 19 2004 Faster approximation algorithms for the minimum latency problem. Zbl 1094.68699 Archer, Aaron; Williamson, David P. 9 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. 8 2002 Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 1017.68157 Ravi, R.; Williamson, D. P. 7 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. 3 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. 60 2001 Adversarial queuing theory. Zbl 1320.68053 Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P. 52 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. 7 2001 Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Zbl 1323.90047 Goemans, Michel X.; Williamson, David 6 2001 Gadgets, approximation, and linear programming. Zbl 0957.68048 Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P. 52 2000 Two-dimensional Gantt charts and a scheduling algorithm of Lawler. Zbl 1054.90032 Goemans, Michel X.; Williamson, David P. 11 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. 8 2000 Improved approximation algorithms for MAX SAT. Zbl 0952.90019 Asano, Takao; 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 A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. Zbl 0962.68068 Khanna, Sanjeev; Sudan, Madhu; Williamson, David P. 18 1999 Improved approximation algorithms for capacitated facility location problems. Zbl 0955.90068 Chudak, Fabián A.; Williamson, David P. 13 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. 5 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. 37 1998 Primal-dual approximation algorithms for feedback problems in planar graphs. Zbl 0928.90094 Goemans, Michel X.; Williamson, David P. 15 1998 An efficient approximation algorithm for the survivable network design problem. Zbl 0922.90140 Gabow, Harold N.; Goemans, Michel X.; Williamson, David P. 11 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. 81 1997 An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 0873.68076 Ravi, R.; Williamson, D. P. 16 1997 Adversarial queueing theory. Zbl 0934.60079 Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P. 10 1996 On the number of small cut in a graph. Zbl 1046.68630 Henzinger, Monika; Williamson, David P. 5 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. 2 1996 Node-disjoint paths on the mesh and a new trade-off in VLSI layout. Zbl 0936.68117 Aggarwal, Alok; Kleinberg, Jon; 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. 785 1995 A general approximation technique for constrained forest problems. Zbl 0834.68055 Goemans, Michel X.; Williamson, David P. 213 1995 Scheduling parallel machines on-line. Zbl 0845.68042 Shmoys, David B.; Wein, Joel; Williamson, David P. 47 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. 36 1995 An approximation algorithm for minimum-cost vertex-connectivity problems. Zbl 0848.05046 Ravi, R.; Williamson, David P. 3 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. 88 1994 .878-approximation algorithms for MAX CUT and MAX 2SAT. Zbl 1345.68274 Goemans, Michel X.; Williamson, David P. 61 1994 New \(3\over4\)-approximation algorithms for the maximum satisfiability problem. Zbl 0812.90129 Goemans, Michel X.; Williamson, David P. 54 1994 Approximating minimum-cost graph problems with spanning tree edges. Zbl 0823.90125 Goemans, Michel X.; Williamson, David P. 10 1994 A note on the prize collecting traveling salesman problem. Zbl 0793.90089 Bienstock, Daniel; Goemans, Michel X.; Simchi-Levi, David; Williamson, David 88 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. 12 1993 An efficient approximation algorithm for the survivable network design problem. Zbl 0923.90136 Gabow, Harold N.; Goemans, Michel X.; Williamson, David P. 10 1993 A new \(\frac{3}{4}\)-approximation algorithm for \(\text{MAX SAT}\). Zbl 0929.90071 Goemans, Michel X.; Williamson, David P. 6 1993 A general approximation technique for constrained forest problems. Zbl 0818.90124 Goemans, Michel X.; Williamson, David P. 29 1992 Scheduling parallel machines on-line. Zbl 0800.68214 Shmoys, David B.; Wein, Joel; Williamson, David P. 9 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. 26 1991 ...and 1 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 3,252 Authors 45 Williamson, David P. 34 Xu, Dachuan 30 Nutov, Zeev 26 Du, Donglei 19 Ravi, Ramamoorthi 19 Wu, Chenchen 18 Kortsarz, Guy 17 Rendl, Franz 16 Anjos, Miguel F. 16 Nagarajan, Viswanath 16 Niedermeier, Rolf 16 Woeginger, Gerhard 15 Shmoys, David B. 13 Escoffier, Bruno 13 Goemans, Michel Xavier 12 Cheriyan, Joseph 12 Feige, Uriel 12 Gupta, Anupam 12 Levin, Asaf 11 Bampis, Evripidis 11 Hajiaghayi, Mohammad Taghi 11 Kowalski, Dariusz R. 11 Lin, Guohui 11 Lisser, Abdel 11 Maffioli, Francesco 11 Saurabh, Saket 11 Wang, Zhenbo 10 Bertsimas, Dimitris John 10 Jonsson, Peter 10 Letchford, Adam N. 10 Mastrolilli, Monaldo 10 Pokutta, Sebastian 10 Sitters, Rene A. 10 Svensson, Ola 10 Sviridenko, Maxim I. 10 Swamy, Chaitanya 10 Xia, Yong 10 Zhang, Peng 9 Ben-Ameur, Walid 9 Chen, Jian-er 9 Chlebus, Bogdan Stanislaw 9 Fiorini, Samuel 9 Jansen, Klaus 9 Khot, Subhash Ajit 9 Kurpisz, Adam 9 Lu, Cheng 9 Naor, Joseph Seffi 9 O’Donnell, Ryan 9 Pardalos, Panos M. 9 Schwartz, Roy 9 Stougie, Leen 8 Chekuri, Chandra S. 8 Epstein, Leah 8 Feldmann, Andreas Emil 8 Könemann, Jochen 8 Laekhanukit, Bundit 8 Laurent, Monique 8 Lee, Jon 8 Li, Jianping 8 Lichen, Junran 8 Nip, Kameng 8 Singer, Amit 8 Trevisan, Luca 8 Vazirani, Vijay V. 8 Vempala, Santosh S. 8 Wiegele, Angelika 8 Xu, Chengxian 8 Živný, Stanislav 7 Bazgan, Cristina 7 Boyd, Sylvia C. 7 Braun, Gábor 7 Buchbinder, Niv 7 Byrka, Jarosław 7 Caragiannis, Ioannis 7 Garg, Naveen Kumar 7 Grandoni, Fabrizio 7 Guo, Jiong 7 Hüffner, Falk 7 Khuller, Samir 7 Komusiewicz, Christian 7 Lau, Lap Chi 7 Lee, Euiwoong 7 Li, Duan 7 Ljubić, Ivana 7 Marathe, Madhav V. 7 Meyer auf der Heide, Friedhelm 7 Neto, José 7 Resende, Mauricio G. C. 7 Segev, Danny 7 Sevastyanov, Sergeĭ Vasil’evich 7 Singh, Mohit 7 Solis-Oba, Roberto 7 van Ee, Martijn 7 van Zuylen, Anke 7 Verschae, José 7 Wang, Jianxin 7 Xing, Wenxun 7 Xu, Fengmin 7 Ye, Yinyu 7 Yu, Xingxing ...and 3,152 more Authors all top 5 Cited in 227 Serials 131 Theoretical Computer Science 122 Mathematical Programming. Series A. Series B 92 Discrete Applied Mathematics 90 Algorithmica 67 Operations Research Letters 65 European Journal of Operational Research 60 Journal of Combinatorial Optimization 45 Journal of Global Optimization 43 Information Processing Letters 36 SIAM Journal on Computing 35 Computers & Operations Research 32 Theory of Computing Systems 31 Journal of Computer and System Sciences 31 Networks 30 Journal of Scheduling 30 Discrete Optimization 29 SIAM Journal on Discrete Mathematics 27 SIAM Journal on Optimization 23 Computational Optimization and Applications 23 Optimization Letters 22 Annals of Operations Research 22 Optimization Methods & Software 17 Operations Research 16 INFORMS Journal on Computing 13 Mathematics of Operations Research 13 International Transactions in Operational Research 13 Journal of the Operations Research Society of China 12 Journal of Combinatorial Theory. Series B 11 Linear Algebra and its Applications 10 Information and Computation 10 Quantum Information Processing 9 Cybernetics and Systems Analysis 9 RAIRO. Operations Research 8 Applied Mathematics and Computation 8 Journal of Computational and Applied Mathematics 8 Journal of Optimization Theory and Applications 8 Random Structures & Algorithms 8 Journal of Machine Learning Research (JMLR) 8 Journal of Industrial and Management Optimization 7 Artificial Intelligence 7 Optimization 7 Journal of Discrete Algorithms 6 Discrete Mathematics 6 Automatica 6 Combinatorica 6 Asia-Pacific Journal of Operational Research 6 Annals of Mathematics and Artificial Intelligence 6 Journal of the ACM 6 Foundations of Computational Mathematics 5 Discrete & Computational Geometry 5 Machine Learning 5 Games and Economic Behavior 5 Bulletin of the American Mathematical Society. New Series 5 Applied and Computational Harmonic Analysis 5 Mathematical Problems in Engineering 5 ACM Journal of Experimental Algorithmics 5 Mathematical Programming Computation 5 Theory of Computing 4 The Annals of Statistics 4 Information Sciences 4 Acta Mathematicae Applicatae Sinica. English Series 4 Journal of Scientific Computing 4 International Journal of Foundations of Computer Science 4 Computational Complexity 4 Discrete Mathematics, Algorithms and Applications 4 Science China. Mathematics 4 ACM Transactions on Algorithms 3 Israel Journal of Mathematics 3 Physica A 3 Computational Geometry 3 Numerical Algorithms 3 SIAM Review 3 Distributed Computing 3 SIAM Journal on Scientific Computing 3 Applied Mathematics. Series B (English Edition) 3 Combinatorics, Probability and Computing 3 International Journal of Computer Vision 3 The Electronic Journal of Combinatorics 3 Top 3 Mathematical Methods of Operations Research 3 CEJOR. Central European Journal of Operations Research 3 4OR 3 SIAM Journal on Imaging Sciences 3 Algorithms 3 Diskretnyĭ Analiz i Issledovanie Operatsiĭ 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 the London Mathematical Society. Second Series 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 ...and 127 more Serials all top 5 Cited in 48 Fields 1,423 Operations research, mathematical programming (90-XX) 1,168 Computer science (68-XX) 453 Combinatorics (05-XX) 102 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 61 Numerical analysis (65-XX) 48 Statistics (62-XX) 31 Probability theory and stochastic processes (60-XX) 30 Quantum theory (81-XX) 27 Linear and multilinear algebra; matrix theory (15-XX) 26 Information and communication theory, circuits (94-XX) 21 Convex and discrete geometry (52-XX) 16 Calculus of variations and optimal control; optimization (49-XX) 14 Algebraic geometry (14-XX) 14 Biology and other natural sciences (92-XX) 14 Systems theory; control (93-XX) 12 Mathematical logic and foundations (03-XX) 12 Functional analysis (46-XX) 11 Statistical mechanics, structure of matter (82-XX) 9 Order, lattices, ordered algebraic structures (06-XX) 5 General and overarching topics; collections (00-XX) 5 General algebraic systems (08-XX) 5 Optics, electromagnetic theory (78-XX) 4 Number theory (11-XX) 4 Commutative algebra (13-XX) 3 Geometry (51-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) 2 Harmonic analysis on Euclidean spaces (42-XX) 2 Operator theory (47-XX) 2 Global analysis, analysis on manifolds (58-XX) 2 Mechanics of deformable solids (74-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 Difference and functional equations (39-XX) 1 Approximations and expansions (41-XX) 1 Abstract harmonic analysis (43-XX) 1 Differential geometry (53-XX) 1 General topology (54-XX) 1 Manifolds and cell complexes (57-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.