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
- 2024
[j72]Renee Mirka
, Devin Smedira, David P. Williamson:
Graph coloring and semidefinite rank. Math. Program. 206(1): 577-605 (2024)- [j71]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
- [j70]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) - [j69]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) - [j68]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) - [j67]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) - [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]