David P. Williamson

ORCID

Publication Activity (10 Years)

Years Active: 1990-2024
Publications (10 Years): 59

Top Venues

Publications

Billy Jin, Nathan Klein, David P. Williamson
A Lower Bound for the Max Entropy Algorithm for TSP. IPCO (2024)
Renee Mirka, David P. Williamson
Max cut and semidefinite rank. Oper. Res. Lett. 53 (2024)
Renee Mirka, Devin Smedira, David P. Williamson
Graph coloring and semidefinite rank. Math. Program. 206 (1) (2024)
Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. Algorithmica 85 (12) (2023)
Henry W. Robbins, Samuel C. Gutekunst, David B. Shmoys, David P. Williamson
GILP: An Interactive Tool for Visualizing the Simplex Algorithm. SIGCSE (1) (2023)
Renee Mirka, David P. Williamson
An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut. ACM J. Exp. Algorithmics 28 (2023)
Santanu Dey, Mohit Singh, David P. Williamson
Special Issue: Integer Programming and Combinatorial Optimization (IPCO) 2021. Math. Program. 197 (2) (2023)
Emmett Breen, Renee Mirka, Zichen Wang, David P. Williamson
Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs. CoRR (2023)
Emmett Breen, Renee Mirka, Zichen Wang, David P. Williamson
-MST Problem in Graphs. SOSA (2023)
Samuel C. Gutekunst, David P. Williamson
The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP. Math. Oper. Res. 48 (1) (2023)
Billy Jin, Nathan Klein, David P. Williamson
A Lower Bound for the Max Entropy Algorithm for TSP. CoRR (2023)
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) (2023)
Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. ITCS (2023)
Billy Jin, Nathan Klein, David P. Williamson
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. IPCO (2023)
Renee Mirka, Devin Smedira, David P. Williamson
Graph Coloring and Semidefinite Rank. CoRR (2022)
Billy Jin, Nathan Klein, David P. Williamson
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. CoRR (2022)
Henry W. Robbins, Samuel C. Gutekunst, Frans Schalekamp, David B. Shmoys, David P. Williamson
GILP: An Interactive Tool for Visualizing the Simplex Algorithm. CoRR (2022)
Renee Mirka, Devin Smedira, David P. Williamson
Graph Coloring and Semidefinite Rank. IPCO (2022)
Joseph (Seffi) Naor, Seeun William Umboh, David P. Williamson
Tight Bounds for Online Weighted Tree Augmentation. Algorithmica 84 (2) (2022)
Samuel C. Gutekunst, David P. Williamson
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps. Math. Oper. Res. 47 (1) (2022)
Samuel C. Gutekunst, Billy Jin, David P. Williamson
The Two-Stripe Symmetric Circulant TSP is in P. CoRR (2022)
Samuel C. Gutekunst, Billy Jin, David P. Williamson
The Two-Stripe Symmetric Circulant TSP is in P. IPCO (2022)
Renee Mirka, David P. Williamson
An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut. SEA (2022)
Billy Jin, David P. Williamson
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model. WINE (2021)
David R. Karger, David P. Williamson
Recursive Random Contraction Revisited. SOSA (2021)
Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson
Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows. CoRR (2021)
Samuel C. Gutekunst, David P. Williamson
The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP. CoRR (2020)
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) (2020)
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)
David R. Karger, David P. Williamson
Recursive Random Contraction Revisited. CoRR (2020)
Billy Jin, David P. Williamson
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching. CoRR (2020)
Samuel C. Gutekunst, David P. Williamson
Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP. Oper. Res. Lett. 48 (3) (2020)
Alice Paul, David P. Williamson
Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing. CoRR (2020)
Monika Henzinger, Billy Jin, David P. Williamson
A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems. CoRR (2020)
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 (2020)
Alice Paul, David P. Williamson
Easy capacitated facility location problems, with connections to lot-sizing. Oper. Res. Lett. 48 (2) (2020)
Samuel C. Gutekunst, David P. Williamson
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem. CoRR (2019)
Samuel C. Gutekunst, David P. Williamson
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP. CoRR (2019)
Daniel Freund, David P. Williamson
Rank aggregation: New bounds for MCx. Discret. Appl. Math. 252 (2019)
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) (2019)
Samuel C. Gutekunst, David P. Williamson
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps. CoRR (2019)
Joseph (Seffi) Naor, Seeun William Umboh, David P. Williamson
Tight Bounds for Online Weighted Tree Augmentation. ICALP (2019)
Joseph Naor, Seeun William Umboh, David P. Williamson
Tight Bounds for Online Weighted Tree Augmentation. CoRR (2019)
Samuel C. Gutekunst, David P. Williamson
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem. SIAM J. Optim. 28 (3) (2018)
Jiawei Qian, Seeun William Umboh, David P. Williamson
Online Constrained Forest and Prize-Collecting Network Design. Algorithmica 80 (11) (2018)
Alice Paul, Matthias Poloczek, David P. Williamson
Simple Approximation Algorithms for Balanced MAX 2SAT. Algorithmica 80 (3) (2018)
Jiawei Qian, Seeun William Umboh, David P. Williamson
Online Constrained Forest and Prize-Collecting Network Design. CoRR (2017)
Kyle Genova, David P. Williamson
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem. Algorithmica 78 (4) (2017)
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) (2017)
Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson
Prize-Collecting TSP with a Budget Constraint. ESA (2017)
Wolfgang Dvorák, Monika Henzinger, David P. Williamson
Maximizing a Submodular Function with Viability Constraints. Algorithmica 77 (1) (2017)
Sin-Shuen Cheung, David P. Williamson
Greedy algorithms for the single-demand facility location problem. Oper. Res. Lett. 45 (5) (2017)
Samuel C. Gutekunst, David P. Williamson
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem. CoRR (2017)
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) (2017)
Matthias Poloczek, David P. Williamson
An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem. ACM J. Exp. Algorithmics 22 (2017)
Matthias Poloczek, David P. Williamson
An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem. SEA (2016)
Alice Paul, Matthias Poloczek, David P. Williamson
Simple Approximation Algorithms for Balanced MAX 2SAT. LATIN (2016)
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) (2016)
Wolfgang Dvorák, Monika Henzinger, David P. Williamson
Maximizing a Submodular Function with Viability Constraints. CoRR (2016)
Kyle Genova, David P. Williamson
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem. ESA (2015)
Daniel Freund, David P. Williamson
MC4, Copeland and restart probabilities. CTW (2015)
Basile Couëtoux, James M. Davis, David P. Williamson
A 3/2-approximation algorithm for some minimum-cost graph problems. Math. Program. 150 (1) (2015)
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) (2015)
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 (2015)
James M. Davis, Huseyin Topaloglu, David P. Williamson
Assortment optimization over time. Oper. Res. Lett. 43 (6) (2015)
Daniel Freund, David P. Williamson
Rank Aggregation: New Bounds for MCx. CoRR (2015)
Kyle Genova, David P. Williamson
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem. CoRR (2015)
Mário César San Felice, David P. Williamson, Orlando Lee
The Online Connected Facility Location Problem. LATIN (2014)
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) (2014)
Anke van Zuylen, Frans Schalekamp, David P. Williamson
Popular ranking. Discret. Appl. Math. 165 (2014)
Matthias Poloczek, David P. Williamson, Anke van Zuylen
On Some Recent Approximation Algorithms for MAX SAT. LATIN (2014)
Wolfgang Dvorák, Monika Henzinger, David P. Williamson
Maximizing a Submodular Function with Viability Constraints. ESA (2013)
Chandrashekhar Nagarajan, David P. Williamson
-Median Algorithms. ACM J. Exp. Algorithmics 18 (2013)
Chandrashekhar Nagarajan, David P. Williamson
Offline and online facility leasing. Discret. Optim. 10 (4) (2013)
Matthias Poloczek, David P. Williamson, Anke van Zuylen
On Some Recent MAX SAT Approximation Algorithms. CoRR (2013)
Frans Schalekamp, David P. Williamson, Anke van Zuylen
A proof of the Boyd-Carr conjecture. SODA (2012)
James M. Davis, David P. Williamson
A Dual-Fitting $\frac{3}{2}$ -Approximation Algorithm for Some Minimum-Cost Graph Problems. ESA (2012)
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)
Anke van Zuylen, Frans Schalekamp, David P. Williamson
Popular Ranking. CTW (2011)
Frans Schalekamp, David P. Williamson, Anke van Zuylen
A Proof of the Boyd-Carr Conjecture CoRR (2011)
Chandrashekhar Nagarajan, David P. Williamson
-Median Algorithms. SEA (2011)
Martin Skutella, David P. Williamson
A note on the generalized min-sum set cover problem CoRR (2011)
Jiawei Qian, David P. Williamson
)-Competitive Algorithm for Online Constrained Forest Problems. ICALP (1) (2011)
Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen
On the Integrality Gap of the Subtour LP for the 1,2-TSP CoRR (2011)
Martin Skutella, David P. Williamson
A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39 (6) (2011)
Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson
A General Approach for Incremental Approximation and Hierarchical Clustering. SIAM J. Comput. 39 (8) (2010)
Mateo Restrepo, David P. Williamson
A simple GAP-canceling algorithm for the generalized maximum flow problem. Math. Program. 118 (1) (2009)
Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson
-edge connected spanning subgraph by LP-rounding. Networks 53 (4) (2009)
Anke van Zuylen, David P. Williamson
Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems. Math. Oper. Res. 34 (3) (2009)
Yogeshwer Sharma, David P. Williamson
Stackelberg thresholds in network routing games or the value of altruism. Games Econ. Behav. 67 (1) (2009)
Chandrashekhar Nagarajan, David P. Williamson
Offline and Online Facility Leasing. IPCO (2008)
Chandrashekhar Nagarajan, Yogeshwer Sharma, David P. Williamson
Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements. WAOA (2008)
Aaron Archer, Asaf Levin, David P. Williamson
A Faster, Better Approximation Algorithm for the Minimum Latency Problem. SIAM J. Comput. 37 (5) (2008)
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) (2007)
Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson
Approximation algorithms for prize collecting forest problems with submodular penalty functions. SODA (2007)
Yogeshwer Sharma, David P. Williamson
Stackelberg thresholds in network routing games or the value of altruism. EC (2007)
Anke van Zuylen, David P. Williamson
Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems. WAOA (2007)
Anke van Zuylen, Rajneesh Hegde, Kamal Jain, David P. Williamson
Deterministic pivoting algorithms for constrained ranking and clustering problems. SODA (2007)
Lisa Fleischer, Kamal Jain, David P. Williamson
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. Syst. Sci. 72 (5) (2006)
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) (2006)

David P. Williamson.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

David P. Williamson