default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDDavid P. Williamson
Person information
- affiliation: Cornell University, Ithaca, USA
- award (2013): Frederick W. Lanchester Prize
- award (2000): Fulkerson Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2025
[j74]Billy Jin
, Nathan Klein, David P. Williamson:
A $\frac{4}{3}$-approximation algorithm for half-integral cycle cut instances of the TSP. Math. Program. 210(1): 511-538 (2025)- 2024
- [j73]Renee Mirka, Devin Smedira, David P. Williamson:
Graph coloring and semidefinite rank. Math. Program. 206(1): 577-605 (2024) - [j72]Renee Mirka, David P. Williamson:
Max cut and semidefinite rank. Oper. Res. Lett. 53: 107067 (2024) - [c60]Billy Jin, Nathan Klein, David P. Williamson:
A Lower Bound for the Max Entropy Algorithm for TSP. IPCO 2024: 238-251 - 2023
- [j71]Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson:
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. Algorithmica 85(12): 3680-3716 (2023) - [j70]Renee Mirka, David P. Williamson:
An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut. ACM J. Exp. Algorithmics 28: 2.1:1-2.1:18 (2023) - [j69]Yicheng Bai, Omar El Housni, Billy Jin, Paat Rusmevichientong, Huseyin Topaloglu, David P. Williamson:
Fluid Approximations for Revenue Management Under High-Variance Demand. Manag. Sci. 69(7): 4016-4026 (2023) - [j68]Samuel C. Gutekunst, David P. Williamson:
The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP. Math. Oper. Res. 48(1): 393-418 (2023) - [j67]Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson:
Erratum to "Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems". Math. Oper. Res. 48(4): 2304-2307 (2023) - [j66]Santanu S. Dey, Mohit Singh, David P. Williamson:
Special Issue: Integer Programming and Combinatorial Optimization (IPCO) 2021. Math. Program. 197(2): 449-450 (2023) - [c59]Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson:
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. ITCS 2023: 69:1-69:22 - [c58]Billy Jin, Nathan Klein, David P. Williamson:
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. IPCO 2023: 217-230 - [c57]Henry W. Robbins, Samuel C. Gutekunst, David B. Shmoys, David P. Williamson:
GILP: An Interactive Tool for Visualizing the Simplex Algorithm. SIGCSE (1) 2023: 108-114 - [c56]Emmett Breen, Renee Mirka, Zichen Wang, David P. Williamson:
Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs. SOSA 2023: 56-68 - [i28]Emmett Breen, Renee Mirka, Zichen Wang, David P. Williamson:
Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs. CoRR abs/2306.01867 (2023) - [i27]Billy Jin, Nathan Klein, David P. Williamson:
A Lower Bound for the Max Entropy Algorithm for TSP. CoRR abs/2311.01950 (2023) - 2022
- [j65]Joseph (Seffi) Naor, Seeun William Umboh, David P. Williamson:
Tight Bounds for Online Weighted Tree Augmentation. Algorithmica 84(2): 304-324 (2022) - [j64]Samuel C. Gutekunst, David P. Williamson:
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps. Math. Oper. Res. 47(1): 1-28 (2022) - [c55]Samuel C. Gutekunst, Billy Jin, David P. Williamson:
The Two-Stripe Symmetric Circulant TSP is in P. IPCO 2022: 319-332 - [c54]Renee Mirka, Devin Smedira, David P. Williamson:
Graph Coloring and Semidefinite Rank. IPCO 2022: 387-401 - [c53]Renee Mirka, David P. Williamson:
An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut. SEA 2022: 19:1-19:14 - [i26]Renee Mirka, Devin Smedira, David P. Williamson:
Graph Coloring and Semidefinite Rank. CoRR abs/2202.10515 (2022) - [i25]Samuel C. Gutekunst, Billy Jin, David P. Williamson:
The Two-Stripe Symmetric Circulant TSP is in P. CoRR abs/2207.10254 (2022) - [i24]Henry W. Robbins, Samuel C. Gutekunst, Frans Schalekamp, David B. Shmoys, David P. Williamson:
GILP: An Interactive Tool for Visualizing the Simplex Algorithm. CoRR abs/2210.15655 (2022) - [i23]Billy Jin, Nathan Klein, David P. Williamson:
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. CoRR abs/2211.04639 (2022) - 2021
- [c52]David R. Karger, David P. Williamson:
Recursive Random Contraction Revisited. SOSA 2021: 68-73 - [c51]Billy Jin, David P. Williamson:
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model. WINE 2021: 207-225 - [e2]Mohit Singh, David P. Williamson:
Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19-21, 2021, Proceedings. Lecture Notes in Computer Science 12707, Springer 2021, ISBN 978-3-030-73878-5 [contents] - [i22]Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson:
Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows. CoRR abs/2109.00653 (2021) - 2020
- [j63]Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson:
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems. Math. Oper. Res. 45(2): 576-590 (2020) - [j62]Alice Paul, David P. Williamson:
Easy capacitated facility location problems, with connections to lot-sizing. Oper. Res. Lett. 48(2): 109-114 (2020) - [j61]Samuel C. Gutekunst, David P. Williamson:
Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP. Oper. Res. Lett. 48(3): 245-248 (2020) - [c50]Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, Madeleine Udell:
Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time. ICMLA 2020: 19-24 - [i21]Alice Paul, David P. Williamson:
Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing. CoRR abs/2001.02727 (2020) - [i20]Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, Madeleine Udell:
Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time. CoRR abs/2006.03750 (2020) - [i19]Billy Jin, David P. Williamson:
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching. CoRR abs/2007.12823 (2020) - [i18]David R. Karger, David P. Williamson:
Recursive Random Contraction Revisited. CoRR abs/2010.15770 (2020) - [i17]Monika Henzinger, Billy Jin, David P. Williamson:
A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems. CoRR abs/2010.16316 (2020) - [i16]Samuel C. Gutekunst, David P. Williamson:
The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP. CoRR abs/2012.12363 (2020)
2010 – 2019
- 2019
- [j60]Daniel Freund, David P. Williamson:
Rank aggregation: New bounds for MCx. Discret. Appl. Math. 252: 28-36 (2019) - [j59]Samuel C. Gutekunst, David P. Williamson:
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem. SIAM J. Discret. Math. 33(4): 2452-2478 (2019) - [c49]Joseph (Seffi) Naor, Seeun William Umboh, David P. Williamson:
Tight Bounds for Online Weighted Tree Augmentation. ICALP 2019: 88:1-88:14 - [i15]Samuel C. Gutekunst, David P. Williamson:
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem. CoRR abs/1902.06808 (2019) - [i14]Joseph Naor, Seeun William Umboh, David P. Williamson:
Tight Bounds for Online Weighted Tree Augmentation. CoRR abs/1904.11777 (2019) - [i13]Samuel C. Gutekunst, David P. Williamson:
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps. CoRR abs/1907.09054 (2019) - [i12]Samuel C. Gutekunst, David P. Williamson:
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP. CoRR abs/1907.11669 (2019) - 2018
- [j58]Alice Paul, Matthias Poloczek, David P. Williamson:
Simple Approximation Algorithms for Balanced MAX 2SAT. Algorithmica 80(3): 995-1012 (2018) - [j57]Jiawei Qian, Seeun William Umboh, David P. Williamson:
Online Constrained Forest and Prize-Collecting Network Design. Algorithmica 80(11): 3335-3364 (2018) - [j56]Samuel C. Gutekunst, David P. Williamson:
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem. SIAM J. Optim. 28(3): 2073-2096 (2018) - 2017
- [j55]Wolfgang Dvorák, Monika Henzinger, David P. Williamson:
Maximizing a Submodular Function with Viability Constraints. Algorithmica 77(1): 152-172 (2017) - [j54]Kyle Genova, David P. Williamson:
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem. Algorithmica 78(4): 1109-1130 (2017) - [j53]James M. Davis, Huseyin Topaloglu, David P. Williamson:
Pricing Problems Under the Nested Logit Model with a Quality Consistency Constraint. INFORMS J. Comput. 29(1): 54-76 (2017) - [j52]Matthias Poloczek, David P. Williamson:
An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem. ACM J. Exp. Algorithmics 22 (2017) - [j51]Sin-Shuen Cheung, David P. Williamson:
Greedy algorithms for the single-demand facility location problem. Oper. Res. Lett. 45(5): 452-455 (2017) - [j50]Matthias Poloczek, Georg Schnitger, David P. Williamson, Anke van Zuylen:
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds. SIAM J. Comput. 46(3): 1029-1061 (2017) - [c48]Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson:
Prize-Collecting TSP with a Budget Constraint. ESA 2017: 62:1-62:14 - [i11]Jiawei Qian, Seeun William Umboh, David P. Williamson:
Online Constrained Forest and Prize-Collecting Network Design. CoRR abs/1702.04871 (2017) - [i10]Samuel C. Gutekunst, David P. Williamson:
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem. CoRR abs/1710.08455 (2017) - 2016
- [j49]Mário César San Felice, David P. Williamson, Orlando Lee:
A Randomized O(log n)-Competitive Algorithm for the Online Connected Facility Location Problem. Algorithmica 76(4): 1139-1157 (2016) - [c47]Alice Paul, Matthias Poloczek, David P. Williamson:
Simple Approximation Algorithms for Balanced MAX 2SAT. LATIN 2016: 659-671 - [c46]Matthias Poloczek, David P. Williamson:
An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem. SEA 2016: 246-261 - [i9]Wolfgang Dvorák, Monika Henzinger, David P. Williamson:
Maximizing a Submodular Function with Viability Constraints. CoRR abs/1611.05753 (2016) - 2015
- [j48]Mário César San Felice, Sin-Shuen Cheung, Orlando Lee, David P. Williamson:
The Online Prize-Collecting Facility Location Problem. Electron. Notes Discret. Math. 50: 151-156 (2015) - [j47]Basile Couëtoux, James M. Davis, David P. Williamson:
A 3/2-approximation algorithm for some minimum-cost graph problems. Math. Program. 150(1): 19-34 (2015) - [j46]Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen:
On the integrality gap of the subtour LP for the 1, 2-TSP. Math. Program. 150(1): 131-151 (2015) - [j45]James M. Davis, Huseyin Topaloglu, David P. Williamson:
Assortment optimization over time. Oper. Res. Lett. 43(6): 608-611 (2015) - [c45]Kyle Genova, David P. Williamson:
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem. ESA 2015: 570-581 - [i8]Daniel Freund, David P. Williamson:
MC4, Copeland and restart probabilities. CTW 2015: 5-8 - [i7]Kyle Genova, David P. Williamson:
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem. CoRR abs/1506.07776 (2015) - [i6]Daniel Freund, David P. Williamson:
Rank Aggregation: New Bounds for MCx. CoRR abs/1510.00738 (2015) - 2014
- [j44]Anke van Zuylen, Frans Schalekamp, David P. Williamson:
Popular ranking. Discret. Appl. Math. 165: 312-316 (2014) - [j43]Frans Schalekamp, David P. Williamson, Anke van Zuylen:
2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture. Math. Oper. Res. 39(2): 403-417 (2014) - [c44]Mário César San Felice, David P. Williamson, Orlando Lee:
The Online Connected Facility Location Problem. LATIN 2014: 574-585 - [c43]Matthias Poloczek, David P. Williamson, Anke van Zuylen:
On Some Recent Approximation Algorithms for MAX SAT. LATIN 2014: 598-609 - 2013
- [j42]Chandrashekhar Nagarajan, David P. Williamson:
Offline and online facility leasing. Discret. Optim. 10(4): 361-370 (2013) - [j41]Chandrashekhar Nagarajan, David P. Williamson:
An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms. ACM J. Exp. Algorithmics 18 (2013) - [c42]Wolfgang Dvorák, Monika Henzinger, David P. Williamson:
Maximizing a Submodular Function with Viability Constraints. ESA 2013: 409-420 - [i5]Matthias Poloczek, David P. Williamson, Anke van Zuylen:
On Some Recent MAX SAT Approximation Algorithms. CoRR abs/1308.3405 (2013) - 2012
- [c41]James M. Davis, David P. Williamson:
A Dual-Fitting $\frac{3}{2}$ -Approximation Algorithm for Some Minimum-Cost Graph Problems. ESA 2012: 373-382 - [c40]Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen:
On the Integrality Gap of the Subtour LP for the 1, 2-TSP. LATIN 2012: 606-617 - [c39]Frans Schalekamp, David P. Williamson, Anke van Zuylen:
A proof of the Boyd-Carr conjecture. SODA 2012: 1477-1486 - 2011
- [b1]David P. Williamson, David B. Shmoys:
The Design of Approximation Algorithms. Cambridge University Press 2011, ISBN 978-0-521-19527-0, pp. I-XI, 1-504 - [j40]Martin Skutella, David P. Williamson:
A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39(6): 433-436 (2011) - [c38]Anke van Zuylen, Frans Schalekamp, David P. Williamson:
Popular Ranking. CTW 2011: 267-270 - [c37]Jiawei Qian, David P. Williamson:
An O(logn)-Competitive Algorithm for Online Constrained Forest Problems. ICALP (1) 2011: 37-48 - [c36]Chandrashekhar Nagarajan, David P. Williamson:
An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms. SEA 2011: 169-180 - [i4]Frans Schalekamp, David P. Williamson, Anke van Zuylen:
A Proof of the Boyd-Carr Conjecture. CoRR abs/1107.1628 (2011) - [i3]Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen:
On the Integrality Gap of the Subtour LP for the 1,2-TSP. CoRR abs/1107.1630 (2011) - [i2]Martin Skutella, David P. Williamson:
A note on the generalized min-sum set cover problem. CoRR abs/1107.2033 (2011) - 2010
- [j39]Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson:
A General Approach for Incremental Approximation and Hierarchical Clustering. SIAM J. Comput. 39(8): 3633-3669 (2010)
2000 – 2009
- 2009
- [j38]Yogeshwer Sharma, David P. Williamson:
Stackelberg thresholds in network routing games or the value of altruism. Games Econ. Behav. 67(1): 174-190 (2009) - [j37]Anke van Zuylen, David P. Williamson:
Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems. Math. Oper. Res. 34(3): 594-620 (2009) - [j36]Mateo Restrepo, David P. Williamson:
A simple GAP-canceling algorithm for the generalized maximum flow problem. Math. Program. 118(1): 47-74 (2009) - [j35]Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson:
Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks 53(4): 345-357 (2009) - 2008
- [j34]Aaron Archer, Asaf Levin, David P. Williamson:
A Faster, Better Approximation Algorithm for the Minimum Latency Problem. SIAM J. Comput. 37(5): 1472-1498 (2008) - [c35]Chandrashekhar Nagarajan, David P. Williamson:
Offline and Online Facility Leasing. IPCO 2008: 303-315 - [c34]Chandrashekhar Nagarajan, Yogeshwer Sharma, David P. Williamson:
Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements. WAOA 2008: 174-187 - 2007
- [j33]David P. Williamson, Anke van Zuylen:
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Oper. Res. Lett. 35(6): 707-712 (2007) - [c33]Yogeshwer Sharma, David P. Williamson:
Stackelberg thresholds in network routing games or the value of altruism. EC 2007: 93-102 - [c32]Anke van Zuylen, Rajneesh Hegde, Kamal Jain, David P. Williamson:
Deterministic pivoting algorithms for constrained ranking and clustering problems. SODA 2007: 405-414 - [c31]Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson:
Approximation algorithms for prize collecting forest problems with submodular penalty functions. SODA 2007: 1275-1284 - [c30]Anke van Zuylen, David P. Williamson:
Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems. WAOA 2007: 260-273 - [e1]Matteo Fischetti, David P. Williamson:
Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings. Lecture Notes in Computer Science 4513, Springer 2007, ISBN 978-3-540-72791-0 [contents] - 2006
- [j32]Lisa Fleischer, Kamal Jain, David P. Williamson:
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. Syst. Sci. 72(5): 838-867 (2006) - [j31]R. N. Uma, Joel Wein, David P. Williamson:
On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems. Theor. Comput. Sci. 361(2-3): 241-256 (2006) - [c29]Paat Rusmevichientong, David P. Williamson:
An adaptive algorithm for selecting profitable keywords for search-based advertising services. EC 2006: 260-269 - [c28]Mateo Restrepo, David P. Williamson:
A simple GAP-canceling algorithm for the generalized maximum flow problem. SODA 2006: 534-543 - [c27]Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson:
A general approach for incremental approximation and hierarchical clustering. SODA 2006: 1147-1156 - 2005
- [j30]Fabián A. Chudak, David P. Williamson:
Improved approximation algorithms for capacitated facility location problems. Math. Program. 102(2): 207-222 (2005) - [c26]Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson:
Approximating the smallest k-edge connected spanning subgraph by LP-rounding. SODA 2005: 562-571 - 2004
- [j29]Michel X. Goemans, David P. Williamson:
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. J. Comput. Syst. Sci. 68(2): 442-470 (2004) - [j28]Fabián A. Chudak, Tim Roughgarden, David P. Williamson:
Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Math. Program. 100(2): 411-421 (2004) - 2003
- [c25]Aaron Archer, David P. Williamson:
Faster approximation algorithms for the minimum latency problem. SODA 2003: 88-96 - [c24]Ronald Fagin, Ravi Kumar, Kevin S. McCurley, Jasmine Novak, D. Sivakumar, John A. Tomlin, David P. Williamson:
Searching the workplace web. WWW 2003: 366-375 - 2002
- [j27]R. Ravi, David P. Williamson:
Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. Algorithmica 34(1): 98-107 (2002) - [j26]Takao Asano, David P. Williamson:
Improved Approximation Algorithms for MAX SAT. J. Algorithms 42(1): 173-202 (2002) - [j25]Kamal Jain, Ion I. Mandoiu, Vijay V. Vazirani, David P. Williamson:
A primal-dual schema based approximation algorithm for the element connectivity problem. J. Algorithms 45(1): 1-15 (2002) - [j24]David P. Williamson:
The primal-dual method for approximation algorithms. Math. Program. 91(3): 447-478 (2002) - [c23]R. Ravi, David P. Williamson:
Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems. SODA 2002: 1000-1001 - 2001
- [j23]Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson:
Adversarial queuing theory. J. ACM 48(1): 13-38 (2001) - [c22]Lisa Fleischer, Kamal Jain, David P. Williamson:
An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem. FOCS 2001: 339-347 - [c21]Fabián A. Chudak, Tim Roughgarden, David P. Williamson:
Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation. IPCO 2001: 60-70 - [c20]Michel X. Goemans, David P. Williamson:
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. STOC 2001: 443-452 - 2000
- [j22]Michel X. Goemans, Joel Wein, David P. Williamson:
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. Oper. Res. Lett. 26(4): 149-154 (2000) - [j21]Alok Aggarwal, Jon M. Kleinberg, David P. Williamson:
Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. SIAM J. Comput. 29(4): 1321-1333 (2000) - [j20]Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson:
Gadgets, Approximation, and Linear Programming. SIAM J. Comput. 29(6): 2074-2097 (2000) - [j19]Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson:
The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. 30(6): 1863-1920 (2000) - [j18]Michel X. Goemans, David P. Williamson:
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SIAM J. Discret. Math. 13(3): 281-294 (2000) - [c19]Takao Asano, David P. Williamson:
Improved approximation algorithms for MAX SAT. SODA 2000: 96-105
1990 – 1999
- 1999
- [c18]Fabián A. Chudak, David P. Williamson:
Improved Approximation Algorithms for Capacitated Facility Location Problems. IPCO 1999: 99-113 - [c17]Michel X. Goemans, David P. Williamson:
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. SODA 1999: 366-375 - [c16]Kamal Jain, Ion I. Mandoiu, Vijay V. Vazirani, David P. Williamson:
A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem. SODA 1999: 484-489 - 1998
- [j17]Michel X. Goemans, David P. Williamson:
Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs. Comb. 18(1): 37-59 (1998) - [j16]Harold N. Gabow, Michel X. Goemans, David P. Williamson:
An efficient approximation algorithm for the survivable network design problem. Math. Program. 82: 13-40 (1998) - [j15]Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson:
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22(4-5): 111-118 (1998) - 1997
- [j14]R. Ravi, David P. Williamson:
An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. Algorithmica 18(1): 21-43 (1997) - [j13]David P. Williamson, Leslie A. Hall, J. A. Hoogeveen, Cor A. J. Hurkens, Jan Karel Lenstra, Sergey Vasil'evich Sevast'janov, David B. Shmoys:
Short Shop Schedules. Oper. Res. 45(2): 288-294 (1997) - [c15]Sanjeev Khanna, Madhu Sudan, David P. Williamson:
A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. STOC 1997: 11-20 - [c14]David P. Williamson:
Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture). WG 1997: 1 - 1996
- [j12]David P. Williamson, Michel X. Goemans:
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. INFORMS J. Comput. 8(1): 29-40 (1996) - [j11]Monika Henzinger, David P. Williamson:
On the Number of Small Cuts in a Graph. Inf. Process. Lett. 59(1): 41-44 (1996) - [c13]Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson:
Gadgets, Approximation, and Linear Programming (extended abstract). FOCS 1996: 617-626 - [c12]Michel X. Goemans, David P. Williamson:
Primal-Dual Approximation Algorithms for Feedback Problems. IPCO 1996: 147-161 - [c11]Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson:
Adversarial Queueing Theory. STOC 1996: 376-385 - [c10]Alok Aggarwal, Jon M. Kleinberg, David P. Williamson:
Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. STOC 1996: 585-594 - [i1]Sanjeev Khanna, Madhu Sudan, David P. Williamson:
A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [j10]David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani:
A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. Comb. 15(3): 435-454 (1995) - [j9]Michel X. Goemans, David P. Williamson:
Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42(6): 1115-1145 (1995) - [j8]Michel X. Goemans, David P. Williamson:
A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput. 24(2): 296-317 (1995) - [j7]David B. Shmoys, Joel Wein, David P. Williamson:
Scheduling Parallel Machines On-Line. SIAM J. Comput. 24(6): 1313-1331 (1995) - 1994
- [j6]Michel X. Goemans, David P. Williamson:
Approximating minimum-cost graph problems with spanning tree edges. Oper. Res. Lett. 16(4): 183-189 (1994) - [j5]Michel X. Goemans, David P. Williamson:
New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem. SIAM J. Discret. Math. 7(4): 656-666 (1994) - [c9]Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, David P. Williamson:
Improved Approximation Algorithms for Network Design Problems. SODA 1994: 223-232 - [c8]David P. Williamson, Michel X. Goemans:
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances. SODA 1994: 355-364 - [c7]Michel X. Goemans, David P. Williamson:
.879-approximation algorithms for MAX CUT and MAX 2SAT. STOC 1994: 422-431 - 1993
- [j4]Daniel Bienstock, Michel X. Goemans, David Simchi-Levi, David P. Williamson:
A note on the prize collecting traveling salesman problem. Math. Program. 59: 413-420 (1993) - [c6]Harold N. Gabow, Michel X. Goemans, David P. Williamson:
An efficient approximation algorithm for the survivable network design problem. IPCO 1993: 57-74 - [c5]Michel X. Goemans, David P. Williamson:
A new \frac34-approximation algorithm for MAX SAT. IPCO 1993: 313-321 - [c4]David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani:
A primal-dual approximation algorithm for generalized Steiner network problems. STOC 1993: 708-717 - 1992
- [j3]David P. Williamson:
Analysis of the Held-Karp lower bound for the asymmetric TSP. Oper. Res. Lett. 12(2): 83-88 (1992) - [c3]Michel X. Goemans, David P. Williamson:
A General Approximation Technique for Constrained Forest Problems. SODA 1992: 307-316 - 1991
- [j2]Chris N. Potts, David B. Shmoys, David P. Williamson:
Permutation vs. non-permutation flow shop schedules. Oper. Res. Lett. 10(5): 281-284 (1991) - [c2]David B. Shmoys, Joel Wein, David P. Williamson:
Scheduling Parallel Machines On-line. On-Line Algorithms 1991: 163-166 - [c1]David B. Shmoys, Joel Wein, David P. Williamson:
Scheduling Parallel Machines On-Line. FOCS 1991: 131-140 - 1990
- [j1]David B. Shmoys, David P. Williamson:
Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application. Inf. Process. Lett. 35(6): 281-285 (1990)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-04-02 01:26 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
