Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: David P. Williamson
@article{DBLP:journals/algorithmica/HenzingerJPW23,
author = {Monika Henzinger and
Billy Jin and
Richard Peng and
David P. Williamson},
title = {A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear
Systems},
journal = {Algorithmica},
volume = {85},
number = {12},
pages = {3680--3716},
year = {2023},
url = {https://doi.org/10.1007/s00453-023-01154-8},
doi = {10.1007/S00453-023-01154-8},
timestamp = {Tue, 21 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/HenzingerJPW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jea/MirkaW23,
author = {Renee Mirka and
David P. Williamson},
title = {An Experimental Evaluation of Semidefinite Programming and Spectral
Algorithms for Max Cut},
journal = {{ACM} J. Exp. Algorithmics},
volume = {28},
pages = {2.1:1--2.1:18},
year = {2023},
url = {https://doi.org/10.1145/3609426},
doi = {10.1145/3609426},
timestamp = {Wed, 24 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jea/MirkaW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mansci/BaiHJRTW23,
author = {Yicheng Bai and
Omar El Housni and
Billy Jin and
Paat Rusmevichientong and
Huseyin Topaloglu and
David P. Williamson},
title = {Fluid Approximations for Revenue Management Under High-Variance Demand},
journal = {Manag. Sci.},
volume = {69},
number = {7},
pages = {4016--4026},
year = {2023},
url = {https://doi.org/10.1287/mnsc.2023.4769},
doi = {10.1287/MNSC.2023.4769},
timestamp = {Sat, 13 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mansci/BaiHJRTW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mor/GutekunstW23,
author = {Samuel C. Gutekunst and
David P. Williamson},
title = {The Circlet Inequalities: {A} New, Circulant-Based, Facet-Defining
Inequality for the {TSP}},
journal = {Math. Oper. Res.},
volume = {48},
number = {1},
pages = {393--418},
year = {2023},
url = {https://doi.org/10.1287/moor.2022.1265},
doi = {10.1287/MOOR.2022.1265},
timestamp = {Fri, 18 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mor/GutekunstW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/DeySW23,
author = {Santanu S. Dey and
Mohit Singh and
David P. Williamson},
title = {Special Issue: Integer Programming and Combinatorial Optimization
{(IPCO)} 2021},
journal = {Math. Program.},
volume = {197},
number = {2},
pages = {449--450},
year = {2023},
url = {https://doi.org/10.1007/s10107-022-01892-7},
doi = {10.1007/S10107-022-01892-7},
timestamp = {Wed, 01 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mp/DeySW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/HenzingerJPW23,
author = {Monika Henzinger and
Billy Jin and
Richard Peng and
David P. Williamson},
editor = {Yael Tauman Kalai},
title = {A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear
Systems},
booktitle = {14th Innovations in Theoretical Computer Science Conference, {ITCS}
2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, {USA}},
series = {LIPIcs},
volume = {251},
pages = {69:1--69:22},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2023.69},
doi = {10.4230/LIPICS.ITCS.2023.69},
timestamp = {Thu, 02 Feb 2023 12:50:42 +0100},
biburl = {https://dblp.org/rec/conf/innovations/HenzingerJPW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/JinKW23,
author = {Billy Jin and
Nathan Klein and
David P. Williamson},
editor = {Alberto Del Pia and
Volker Kaibel},
title = {A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances
of the {TSP}},
booktitle = {Integer Programming and Combinatorial Optimization - 24th International
Conference, {IPCO} 2023, Madison, WI, USA, June 21-23, 2023, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {13904},
pages = {217--230},
publisher = {Springer},
year = {2023},
url = {https://doi.org/10.1007/978-3-031-32726-1\_16},
doi = {10.1007/978-3-031-32726-1\_16},
timestamp = {Fri, 02 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/ipco/JinKW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sigcse/RobbinsGSW23,
author = {Henry W. Robbins and
Samuel C. Gutekunst and
David B. Shmoys and
David P. Williamson},
editor = {Maureen Doyle and
Ben Stephenson and
Brian Dorn and
Leen{-}Kiat Soh and
Lina Battestilli},
title = {{GILP:} An Interactive Tool for Visualizing the Simplex Algorithm},
booktitle = {Proceedings of the 54th {ACM} Technical Symposium on Computer Science
Education, Volume 1, {SIGCSE} 2023, Toronto, ON, Canada, March 15-18,
2023},
pages = {108--114},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3545945.3569815},
doi = {10.1145/3545945.3569815},
timestamp = {Sat, 11 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/sigcse/RobbinsGSW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sosa/BreenMWW23,
author = {Emmett Breen and
Renee Mirka and
Zichen Wang and
David P. Williamson},
editor = {Telikepalli Kavitha and
Kurt Mehlhorn},
title = {Revisiting Garg's 2-Approximation Algorithm for the \emph{k}-MST Problem
in Graphs},
booktitle = {2023 Symposium on Simplicity in Algorithms, {SOSA} 2023, Florence,
Italy, January 23-25, 2023},
pages = {56--68},
publisher = {{SIAM}},
year = {2023},
url = {https://doi.org/10.1137/1.9781611977585.ch6},
doi = {10.1137/1.9781611977585.CH6},
timestamp = {Mon, 20 Mar 2023 16:52:56 +0100},
biburl = {https://dblp.org/rec/conf/sosa/BreenMWW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2306-01867,
author = {Emmett Breen and
Renee Mirka and
Zichen Wang and
David P. Williamson},
title = {Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem
in Graphs},
journal = {CoRR},
volume = {abs/2306.01867},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2306.01867},
doi = {10.48550/ARXIV.2306.01867},
eprinttype = {arXiv},
eprint = {2306.01867},
timestamp = {Mon, 12 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2306-01867.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2311-01950,
author = {Billy Jin and
Nathan Klein and
David P. Williamson},
title = {A Lower Bound for the Max Entropy Algorithm for {TSP}},
journal = {CoRR},
volume = {abs/2311.01950},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2311.01950},
doi = {10.48550/ARXIV.2311.01950},
eprinttype = {arXiv},
eprint = {2311.01950},
timestamp = {Tue, 07 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2311-01950.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/NaorUW22,
author = {Joseph (Seffi) Naor and
Seeun William Umboh and
David P. Williamson},
title = {Tight Bounds for Online Weighted Tree Augmentation},
journal = {Algorithmica},
volume = {84},
number = {2},
pages = {304--324},
year = {2022},
url = {https://doi.org/10.1007/s00453-021-00888-7},
doi = {10.1007/S00453-021-00888-7},
timestamp = {Wed, 23 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/NaorUW22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mor/GutekunstW22,
author = {Samuel C. Gutekunst and
David P. Williamson},
title = {Semidefinite Programming Relaxations of the Traveling Salesman Problem
and Their Integrality Gaps},
journal = {Math. Oper. Res.},
volume = {47},
number = {1},
pages = {1--28},
year = {2022},
url = {https://doi.org/10.1287/moor.2020.1100},
doi = {10.1287/MOOR.2020.1100},
timestamp = {Thu, 25 Aug 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mor/GutekunstW22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/GutekunstJW22,
author = {Samuel C. Gutekunst and
Billy Jin and
David P. Williamson},
editor = {Karen I. Aardal and
Laura Sanit{\`{a}}},
title = {The Two-Stripe Symmetric Circulant {TSP} is in {P}},
booktitle = {Integer Programming and Combinatorial Optimization - 23rd International
Conference, {IPCO} 2022, Eindhoven, The Netherlands, June 27-29, 2022,
Proceedings},
series = {Lecture Notes in Computer Science},
volume = {13265},
pages = {319--332},
publisher = {Springer},
year = {2022},
url = {https://doi.org/10.1007/978-3-031-06901-7\_24},
doi = {10.1007/978-3-031-06901-7\_24},
timestamp = {Tue, 25 Jul 2023 13:14:28 +0200},
biburl = {https://dblp.org/rec/conf/ipco/GutekunstJW22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/MirkaSW22,
author = {Renee Mirka and
Devin Smedira and
David P. Williamson},
editor = {Karen I. Aardal and
Laura Sanit{\`{a}}},
title = {Graph Coloring and Semidefinite Rank},
booktitle = {Integer Programming and Combinatorial Optimization - 23rd International
Conference, {IPCO} 2022, Eindhoven, The Netherlands, June 27-29, 2022,
Proceedings},
series = {Lecture Notes in Computer Science},
volume = {13265},
pages = {387--401},
publisher = {Springer},
year = {2022},
url = {https://doi.org/10.1007/978-3-031-06901-7\_29},
doi = {10.1007/978-3-031-06901-7\_29},
timestamp = {Mon, 30 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/ipco/MirkaSW22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wea/MirkaW22,
author = {Renee Mirka and
David P. Williamson},
editor = {Christian Schulz and
Bora U{\c{c}}ar},
title = {An Experimental Evaluation of Semidefinite Programming and Spectral
Algorithms for Max Cut},
booktitle = {20th International Symposium on Experimental Algorithms, {SEA} 2022,
July 25-27, 2022, Heidelberg, Germany},
series = {LIPIcs},
volume = {233},
pages = {19:1--19:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.SEA.2022.19},
doi = {10.4230/LIPICS.SEA.2022.19},
timestamp = {Mon, 11 Jul 2022 14:59:46 +0200},
biburl = {https://dblp.org/rec/conf/wea/MirkaW22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2202-10515,
author = {Renee Mirka and
Devin Smedira and
David P. Williamson},
title = {Graph Coloring and Semidefinite Rank},
journal = {CoRR},
volume = {abs/2202.10515},
year = {2022},
url = {https://arxiv.org/abs/2202.10515},
eprinttype = {arXiv},
eprint = {2202.10515},
timestamp = {Thu, 03 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2202-10515.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2207-10254,
author = {Samuel C. Gutekunst and
Billy Jin and
David P. Williamson},
title = {The Two-Stripe Symmetric Circulant {TSP} is in {P}},
journal = {CoRR},
volume = {abs/2207.10254},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2207.10254},
doi = {10.48550/ARXIV.2207.10254},
eprinttype = {arXiv},
eprint = {2207.10254},
timestamp = {Mon, 25 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2207-10254.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2210-15655,
author = {Henry W. Robbins and
Samuel C. Gutekunst and
Frans Schalekamp and
David B. Shmoys and
David P. Williamson},
title = {{GILP:} An Interactive Tool for Visualizing the Simplex Algorithm},
journal = {CoRR},
volume = {abs/2210.15655},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2210.15655},
doi = {10.48550/ARXIV.2210.15655},
eprinttype = {arXiv},
eprint = {2210.15655},
timestamp = {Wed, 02 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2210-15655.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2211-04639,
author = {Billy Jin and
Nathan Klein and
David P. Williamson},
title = {A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances
of the {TSP}},
journal = {CoRR},
volume = {abs/2211.04639},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2211.04639},
doi = {10.48550/ARXIV.2211.04639},
eprinttype = {arXiv},
eprint = {2211.04639},
timestamp = {Tue, 15 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2211-04639.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sosa/KargerW21,
author = {David R. Karger and
David P. Williamson},
editor = {Hung Viet Le and
Valerie King},
title = {Recursive Random Contraction Revisited},
booktitle = {4th Symposium on Simplicity in Algorithms, {SOSA} 2021, Virtual Conference,
January 11-12, 2021},
pages = {68--73},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976496.7},
doi = {10.1137/1.9781611976496.7},
timestamp = {Wed, 17 Mar 2021 13:30:03 +0100},
biburl = {https://dblp.org/rec/conf/sosa/KargerW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wine/JinW21,
author = {Billy Jin and
David P. Williamson},
editor = {Michal Feldman and
Hu Fu and
Inbal Talgam{-}Cohen},
title = {Improved Analysis of {RANKING} for Online Vertex-Weighted Bipartite
Matching in the Random Order Model},
booktitle = {Web and Internet Economics - 17th International Conference, {WINE}
2021, Potsdam, Germany, December 14-17, 2021, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {13112},
pages = {207--225},
publisher = {Springer},
year = {2021},
url = {https://doi.org/10.1007/978-3-030-94676-0\_12},
doi = {10.1007/978-3-030-94676-0\_12},
timestamp = {Mon, 30 Oct 2023 12:09:00 +0100},
biburl = {https://dblp.org/rec/conf/wine/JinW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/ipco/2021,
editor = {Mohit Singh and
David P. Williamson},
title = {Integer Programming and Combinatorial Optimization - 22nd International
Conference, {IPCO} 2021, Atlanta, GA, USA, May 19-21, 2021, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {12707},
publisher = {Springer},
year = {2021},
url = {https://doi.org/10.1007/978-3-030-73879-2},
doi = {10.1007/978-3-030-73879-2},
isbn = {978-3-030-73878-5},
timestamp = {Thu, 06 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/ipco/2021.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2109-00653,
author = {Monika Henzinger and
Billy Jin and
Richard Peng and
David P. Williamson},
title = {Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm
Flows},
journal = {CoRR},
volume = {abs/2109.00653},
year = {2021},
url = {https://arxiv.org/abs/2109.00653},
eprinttype = {arXiv},
eprint = {2109.00653},
timestamp = {Mon, 20 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2109-00653.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mor/PaulFFSW20,
author = {Alice Paul and
Daniel Freund and
Aaron M. Ferber and
David B. Shmoys and
David P. Williamson},
title = {Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning
Tree Problems},
journal = {Math. Oper. Res.},
volume = {45},
number = {2},
pages = {576--590},
year = {2020},
url = {https://doi.org/10.1287/moor.2019.1002},
doi = {10.1287/MOOR.2019.1002},
timestamp = {Wed, 07 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mor/PaulFFSW20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/PaulW20,
author = {Alice Paul and
David P. Williamson},
title = {Easy capacitated facility location problems, with connections to lot-sizing},
journal = {Oper. Res. Lett.},
volume = {48},
number = {2},
pages = {109--114},
year = {2020},
url = {https://doi.org/10.1016/j.orl.2019.12.006},
doi = {10.1016/J.ORL.2019.12.006},
timestamp = {Mon, 19 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/orl/PaulW20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/GutekunstW20,
author = {Samuel C. Gutekunst and
David P. Williamson},
title = {Subtour elimination constraints imply a matrix-tree theorem {SDP}
constraint for the {TSP}},
journal = {Oper. Res. Lett.},
volume = {48},
number = {3},
pages = {245--248},
year = {2020},
url = {https://doi.org/10.1016/j.orl.2020.02.011},
doi = {10.1016/J.ORL.2020.02.011},
timestamp = {Mon, 19 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/orl/GutekunstW20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icmla/DroriKSKMGDDWU20,
author = {Iddo Drori and
Anant Kharkar and
William R. Sickinger and
Brandon Kates and
Qiang Ma and
Suwen Ge and
Eden Dolev and
Brenda Dietrich and
David P. Williamson and
Madeleine Udell},
editor = {M. Arif Wani and
Feng Luo and
Xiaolin Andy Li and
Dejing Dou and
Francesco Bonchi},
title = {Learning to Solve Combinatorial Optimization Problems on Real-World
Graphs in Linear Time},
booktitle = {19th {IEEE} International Conference on Machine Learning and Applications,
{ICMLA} 2020, Miami, FL, USA, December 14-17, 2020},
pages = {19--24},
publisher = {{IEEE}},
year = {2020},
url = {https://doi.org/10.1109/ICMLA51294.2020.00013},
doi = {10.1109/ICMLA51294.2020.00013},
timestamp = {Mon, 25 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icmla/DroriKSKMGDDWU20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2001-02727,
author = {Alice Paul and
David P. Williamson},
title = {Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing},
journal = {CoRR},
volume = {abs/2001.02727},
year = {2020},
url = {http://arxiv.org/abs/2001.02727},
eprinttype = {arXiv},
eprint = {2001.02727},
timestamp = {Mon, 13 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2001-02727.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2006-03750,
author = {Iddo Drori and
Anant Kharkar and
William R. Sickinger and
Brandon Kates and
Qiang Ma and
Suwen Ge and
Eden Dolev and
Brenda Dietrich and
David P. Williamson and
Madeleine Udell},
title = {Learning to Solve Combinatorial Optimization Problems on Real-World
Graphs in Linear Time},
journal = {CoRR},
volume = {abs/2006.03750},
year = {2020},
url = {https://arxiv.org/abs/2006.03750},
eprinttype = {arXiv},
eprint = {2006.03750},
timestamp = {Tue, 26 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2006-03750.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2007-12823,
author = {Billy Jin and
David P. Williamson},
title = {Improved Analysis of {RANKING} for Online Vertex-Weighted Bipartite
Matching},
journal = {CoRR},
volume = {abs/2007.12823},
year = {2020},
url = {https://arxiv.org/abs/2007.12823},
eprinttype = {arXiv},
eprint = {2007.12823},
timestamp = {Wed, 29 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2007-12823.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2010-15770,
author = {David R. Karger and
David P. Williamson},
title = {Recursive Random Contraction Revisited},
journal = {CoRR},
volume = {abs/2010.15770},
year = {2020},
url = {https://arxiv.org/abs/2010.15770},
eprinttype = {arXiv},
eprint = {2010.15770},
timestamp = {Tue, 03 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2010-15770.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2010-16316,
author = {Monika Henzinger and
Billy Jin and
David P. Williamson},
title = {A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems},
journal = {CoRR},
volume = {abs/2010.16316},
year = {2020},
url = {https://arxiv.org/abs/2010.16316},
eprinttype = {arXiv},
eprint = {2010.16316},
timestamp = {Tue, 03 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2010-16316.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2012-12363,
author = {Samuel C. Gutekunst and
David P. Williamson},
title = {The Circlet Inequalities: {A} New, Circulant-Based Facet-Defining
Inequality for the {TSP}},
journal = {CoRR},
volume = {abs/2012.12363},
year = {2020},
url = {https://arxiv.org/abs/2012.12363},
eprinttype = {arXiv},
eprint = {2012.12363},
timestamp = {Tue, 05 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2012-12363.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dam/FreundW19,
author = {Daniel Freund and
David P. Williamson},
title = {Rank aggregation: New bounds for MCx},
journal = {Discret. Appl. Math.},
volume = {252},
pages = {28--36},
year = {2019},
url = {https://doi.org/10.1016/j.dam.2017.07.020},
doi = {10.1016/J.DAM.2017.07.020},
timestamp = {Thu, 20 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dam/FreundW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamdm/GutekunstW19,
author = {Samuel C. Gutekunst and
David P. Williamson},
title = {Characterizing the Integrality Gap of the Subtour {LP} for the Circulant
Traveling Salesman Problem},
journal = {{SIAM} J. Discret. Math.},
volume = {33},
number = {4},
pages = {2452--2478},
year = {2019},
url = {https://doi.org/10.1137/19M1245840},
doi = {10.1137/19M1245840},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/GutekunstW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/NaorUW19,
author = {Joseph (Seffi) Naor and
Seeun William Umboh and
David P. Williamson},
editor = {Christel Baier and
Ioannis Chatzigiannakis and
Paola Flocchini and
Stefano Leonardi},
title = {Tight Bounds for Online Weighted Tree Augmentation},
booktitle = {46th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2019, July 9-12, 2019, Patras, Greece},
series = {LIPIcs},
volume = {132},
pages = {88:1--88:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2019.88},
doi = {10.4230/LIPICS.ICALP.2019.88},
timestamp = {Tue, 27 Dec 2022 09:06:31 +0100},
biburl = {https://dblp.org/rec/conf/icalp/NaorUW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1902-06808,
author = {Samuel C. Gutekunst and
David P. Williamson},
title = {Characterizing the Integrality Gap of the Subtour {LP} for the Circulant
Traveling Salesman Problem},
journal = {CoRR},
volume = {abs/1902.06808},
year = {2019},
url = {http://arxiv.org/abs/1902.06808},
eprinttype = {arXiv},
eprint = {1902.06808},
timestamp = {Tue, 21 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1902-06808.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1904-11777,
author = {Joseph Naor and
Seeun William Umboh and
David P. Williamson},
title = {Tight Bounds for Online Weighted Tree Augmentation},
journal = {CoRR},
volume = {abs/1904.11777},
year = {2019},
url = {http://arxiv.org/abs/1904.11777},
eprinttype = {arXiv},
eprint = {1904.11777},
timestamp = {Thu, 02 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1904-11777.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1907-09054,
author = {Samuel C. Gutekunst and
David P. Williamson},
title = {Semidefinite Programming Relaxations of the Traveling Salesman Problem
and Their Integrality Gaps},
journal = {CoRR},
volume = {abs/1907.09054},
year = {2019},
url = {http://arxiv.org/abs/1907.09054},
eprinttype = {arXiv},
eprint = {1907.09054},
timestamp = {Tue, 30 Jul 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1907-09054.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1907-11669,
author = {Samuel C. Gutekunst and
David P. Williamson},
title = {Subtour Elimination Constraints Imply a Matrix-Tree Theorem {SDP}
Constraint for the {TSP}},
journal = {CoRR},
volume = {abs/1907.11669},
year = {2019},
url = {http://arxiv.org/abs/1907.11669},
eprinttype = {arXiv},
eprint = {1907.11669},
timestamp = {Thu, 01 Aug 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1907-11669.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/PaulPW18,
author = {Alice Paul and
Matthias Poloczek and
David P. Williamson},
title = {Simple Approximation Algorithms for Balanced {MAX} 2SAT},
journal = {Algorithmica},
volume = {80},
number = {3},
pages = {995--1012},
year = {2018},
url = {https://doi.org/10.1007/s00453-017-0312-6},
doi = {10.1007/S00453-017-0312-6},
timestamp = {Thu, 15 Feb 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/PaulPW18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/QianUW18,
author = {Jiawei Qian and
Seeun William Umboh and
David P. Williamson},
title = {Online Constrained Forest and Prize-Collecting Network Design},
journal = {Algorithmica},
volume = {80},
number = {11},
pages = {3335--3364},
year = {2018},
url = {https://doi.org/10.1007/s00453-017-0391-4},
doi = {10.1007/S00453-017-0391-4},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/QianUW18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamjo/GutekunstW18,
author = {Samuel C. Gutekunst and
David P. Williamson},
title = {The Unbounded Integrality Gap of a Semidefinite Relaxation of the
Traveling Salesman Problem},
journal = {{SIAM} J. Optim.},
volume = {28},
number = {3},
pages = {2073--2096},
year = {2018},
url = {https://doi.org/10.1137/17M1154722},
doi = {10.1137/17M1154722},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamjo/GutekunstW18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/DvorakHW17,
author = {Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
David P. Williamson},
title = {Maximizing a Submodular Function with Viability Constraints},
journal = {Algorithmica},
volume = {77},
number = {1},
pages = {152--172},
year = {2017},
url = {https://doi.org/10.1007/s00453-015-0066-y},
doi = {10.1007/S00453-015-0066-Y},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/DvorakHW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/GenovaW17,
author = {Kyle Genova and
David P. Williamson},
title = {An Experimental Evaluation of the Best-of-Many Christofides' Algorithm
for the Traveling Salesman Problem},
journal = {Algorithmica},
volume = {78},
number = {4},
pages = {1109--1130},
year = {2017},
url = {https://doi.org/10.1007/s00453-017-0293-5},
doi = {10.1007/S00453-017-0293-5},
timestamp = {Wed, 26 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/GenovaW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/informs/DavisTW17,
author = {James M. Davis and
Huseyin Topaloglu and
David P. Williamson},
title = {Pricing Problems Under the Nested Logit Model with a Quality Consistency
Constraint},
journal = {{INFORMS} J. Comput.},
volume = {29},
number = {1},
pages = {54--76},
year = {2017},
url = {https://doi.org/10.1287/ijoc.2016.0714},
doi = {10.1287/IJOC.2016.0714},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/informs/DavisTW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jea/PoloczekW17,
author = {Matthias Poloczek and
David P. Williamson},
title = {An Experimental Evaluation of Fast Approximation Algorithms for the
Maximum Satisfiability Problem},
journal = {{ACM} J. Exp. Algorithmics},
volume = {22},
year = {2017},
url = {https://doi.org/10.1145/3064174},
doi = {10.1145/3064174},
timestamp = {Sat, 08 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jea/PoloczekW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/CheungW17,
author = {Sin{-}Shuen Cheung and
David P. Williamson},
title = {Greedy algorithms for the single-demand facility location problem},
journal = {Oper. Res. Lett.},
volume = {45},
number = {5},
pages = {452--455},
year = {2017},
url = {https://doi.org/10.1016/j.orl.2017.07.002},
doi = {10.1016/J.ORL.2017.07.002},
timestamp = {Thu, 28 Dec 2017 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/orl/CheungW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/PoloczekSWZ17,
author = {Matthias Poloczek and
Georg Schnitger and
David P. Williamson and
Anke van Zuylen},
title = {Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms
and Inapproximability Bounds},
journal = {{SIAM} J. Comput.},
volume = {46},
number = {3},
pages = {1029--1061},
year = {2017},
url = {https://doi.org/10.1137/15M1053369},
doi = {10.1137/15M1053369},
timestamp = {Wed, 05 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/PoloczekSWZ17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/Paul0FSW17,
author = {Alice Paul and
Daniel Freund and
Aaron M. Ferber and
David B. Shmoys and
David P. Williamson},
editor = {Kirk Pruhs and
Christian Sohler},
title = {Prize-Collecting {TSP} with a Budget Constraint},
booktitle = {25th Annual European Symposium on Algorithms, {ESA} 2017, September
4-6, 2017, Vienna, Austria},
series = {LIPIcs},
volume = {87},
pages = {62:1--62:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ESA.2017.62},
doi = {10.4230/LIPICS.ESA.2017.62},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/esa/Paul0FSW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/QianUW17,
author = {Jiawei Qian and
Seeun William Umboh and
David P. Williamson},
title = {Online Constrained Forest and Prize-Collecting Network Design},
journal = {CoRR},
volume = {abs/1702.04871},
year = {2017},
url = {http://arxiv.org/abs/1702.04871},
eprinttype = {arXiv},
eprint = {1702.04871},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/QianUW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1710-08455,
author = {Samuel C. Gutekunst and
David P. Williamson},
title = {The Unbounded Integrality Gap of a Semidefinite Relaxation of the
Traveling Salesman Problem},
journal = {CoRR},
volume = {abs/1710.08455},
year = {2017},
url = {http://arxiv.org/abs/1710.08455},
eprinttype = {arXiv},
eprint = {1710.08455},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1710-08455.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/FeliceWL16,
author = {M{\'{a}}rio C{\'{e}}sar San Felice and
David P. Williamson and
Orlando Lee},
title = {A Randomized O(log n)-Competitive Algorithm for the Online Connected
Facility Location Problem},
journal = {Algorithmica},
volume = {76},
number = {4},
pages = {1139--1157},
year = {2016},
url = {https://doi.org/10.1007/s00453-016-0115-1},
doi = {10.1007/S00453-016-0115-1},
timestamp = {Fri, 30 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/FeliceWL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/latin/PaulPW16,
author = {Alice Paul and
Matthias Poloczek and
David P. Williamson},
editor = {Evangelos Kranakis and
Gonzalo Navarro and
Edgar Ch{\'{a}}vez},
title = {Simple Approximation Algorithms for Balanced {MAX} 2SAT},
booktitle = {{LATIN} 2016: Theoretical Informatics - 12th Latin American Symposium,
Ensenada, Mexico, April 11-15, 2016, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {9644},
pages = {659--671},
publisher = {Springer},
year = {2016},
url = {https://doi.org/10.1007/978-3-662-49529-2\_49},
doi = {10.1007/978-3-662-49529-2\_49},
timestamp = {Wed, 28 Feb 2024 00:16:41 +0100},
biburl = {https://dblp.org/rec/conf/latin/PaulPW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wea/PoloczekW16,
author = {Matthias Poloczek and
David P. Williamson},
editor = {Andrew V. Goldberg and
Alexander S. Kulikov},
title = {An Experimental Evaluation of Fast Approximation Algorithms for the
Maximum Satisfiability Problem},
booktitle = {Experimental Algorithms - 15th International Symposium, {SEA} 2016,
St. Petersburg, Russia, June 5-8, 2016, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {9685},
pages = {246--261},
publisher = {Springer},
year = {2016},
url = {https://doi.org/10.1007/978-3-319-38851-9\_17},
doi = {10.1007/978-3-319-38851-9\_17},
timestamp = {Tue, 14 May 2019 10:00:42 +0200},
biburl = {https://dblp.org/rec/conf/wea/PoloczekW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/DvorakHW16,
author = {Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
David P. Williamson},
title = {Maximizing a Submodular Function with Viability Constraints},
journal = {CoRR},
volume = {abs/1611.05753},
year = {2016},
url = {http://arxiv.org/abs/1611.05753},
eprinttype = {arXiv},
eprint = {1611.05753},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/DvorakHW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/endm/FeliceCLW15,
author = {M{\'{a}}rio C{\'{e}}sar San Felice and
Sin{-}Shuen Cheung and
Orlando Lee and
David P. Williamson},
title = {The Online Prize-Collecting Facility Location Problem},
journal = {Electron. Notes Discret. Math.},
volume = {50},
pages = {151--156},
year = {2015},
url = {https://doi.org/10.1016/j.endm.2015.07.026},
doi = {10.1016/J.ENDM.2015.07.026},
timestamp = {Thu, 20 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/endm/FeliceCLW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/CouetouxDW15,
author = {Basile Cou{\"{e}}toux and
James M. Davis and
David P. Williamson},
title = {A 3/2-approximation algorithm for some minimum-cost graph problems},
journal = {Math. Program.},
volume = {150},
number = {1},
pages = {19--34},
year = {2015},
url = {https://doi.org/10.1007/s10107-013-0727-z},
doi = {10.1007/S10107-013-0727-Z},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mp/CouetouxDW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/QianSWZ15,
author = {Jiawei Qian and
Frans Schalekamp and
David P. Williamson and
Anke van Zuylen},
title = {On the integrality gap of the subtour {LP} for the 1, 2-TSP},
journal = {Math. Program.},
volume = {150},
number = {1},
pages = {131--151},
year = {2015},
url = {https://doi.org/10.1007/s10107-014-0835-4},
doi = {10.1007/S10107-014-0835-4},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mp/QianSWZ15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/DavisTW15,
author = {James M. Davis and
Huseyin Topaloglu and
David P. Williamson},
title = {Assortment optimization over time},
journal = {Oper. Res. Lett.},
volume = {43},
number = {6},
pages = {608--611},
year = {2015},
url = {https://doi.org/10.1016/j.orl.2015.08.007},
doi = {10.1016/J.ORL.2015.08.007},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/orl/DavisTW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/GenovaW15,
author = {Kyle Genova and
David P. Williamson},
editor = {Nikhil Bansal and
Irene Finocchi},
title = {An Experimental Evaluation of the Best-of-Many Christofides' Algorithm
for the Traveling Salesman Problem},
booktitle = {Algorithms - {ESA} 2015 - 23rd Annual European Symposium, Patras,
Greece, September 14-16, 2015, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {9294},
pages = {570--581},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-662-48350-3\_48},
doi = {10.1007/978-3-662-48350-3\_48},
timestamp = {Tue, 15 Feb 2022 07:54:27 +0100},
biburl = {https://dblp.org/rec/conf/esa/GenovaW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colognetwente/FreundW15,
author = {Daniel Freund and
David P. Williamson},
editor = {Ekrem Duman and
Ali Fuat Alkaya},
title = {MC4, Copeland and restart probabilities},
booktitle = {13th Cologne Twente Workshop on Graphs and Combinatorial Optimization,
Istanbul, Turkey, May 26-28, 2015},
pages = {5--8},
year = {2015},
timestamp = {Thu, 02 Feb 2017 18:00:28 +0100},
biburl = {https://dblp.org/rec/conf/colognetwente/FreundW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/GenovaW15,
author = {Kyle Genova and
David P. Williamson},
title = {An Experimental Evaluation of the Best-of-Many Christofides' Algorithm
for the Traveling Salesman Problem},
journal = {CoRR},
volume = {abs/1506.07776},
year = {2015},
url = {http://arxiv.org/abs/1506.07776},
eprinttype = {arXiv},
eprint = {1506.07776},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/GenovaW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/FreundW15,
author = {Daniel Freund and
David P. Williamson},
title = {Rank Aggregation: New Bounds for MCx},
journal = {CoRR},
volume = {abs/1510.00738},
year = {2015},
url = {http://arxiv.org/abs/1510.00738},
eprinttype = {arXiv},
eprint = {1510.00738},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/FreundW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dam/ZuylenSW14,
author = {Anke van Zuylen and
Frans Schalekamp and
David P. Williamson},
title = {Popular ranking},
journal = {Discret. Appl. Math.},
volume = {165},
pages = {312--316},
year = {2014},
url = {https://doi.org/10.1016/j.dam.2012.07.006},
doi = {10.1016/J.DAM.2012.07.006},
timestamp = {Thu, 11 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dam/ZuylenSW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mor/SchalekampWZ14,
author = {Frans Schalekamp and
David P. Williamson and
Anke van Zuylen},
title = {2-Matchings, the Traveling Salesman Problem, and the Subtour {LP:}
{A} Proof of the Boyd-Carr Conjecture},
journal = {Math. Oper. Res.},
volume = {39},
number = {2},
pages = {403--417},
year = {2014},
url = {https://doi.org/10.1287/moor.2013.0608},
doi = {10.1287/MOOR.2013.0608},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mor/SchalekampWZ14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/latin/FeliceWL14,
author = {M{\'{a}}rio C{\'{e}}sar San Felice and
David P. Williamson and
Orlando Lee},
editor = {Alberto Pardo and
Alfredo Viola},
title = {The Online Connected Facility Location Problem},
booktitle = {{LATIN} 2014: Theoretical Informatics - 11th Latin American Symposium,
Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8392},
pages = {574--585},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-642-54423-1\_50},
doi = {10.1007/978-3-642-54423-1\_50},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/latin/FeliceWL14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/latin/PoloczekWZ14,
author = {Matthias Poloczek and
David P. Williamson and
Anke van Zuylen},
editor = {Alberto Pardo and
Alfredo Viola},
title = {On Some Recent Approximation Algorithms for {MAX} {SAT}},
booktitle = {{LATIN} 2014: Theoretical Informatics - 11th Latin American Symposium,
Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8392},
pages = {598--609},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-642-54423-1\_52},
doi = {10.1007/978-3-642-54423-1\_52},
timestamp = {Tue, 23 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/latin/PoloczekWZ14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/disopt/NagarajanW13,
author = {Chandrashekhar Nagarajan and
David P. Williamson},
title = {Offline and online facility leasing},
journal = {Discret. Optim.},
volume = {10},
number = {4},
pages = {361--370},
year = {2013},
url = {https://doi.org/10.1016/j.disopt.2013.10.001},
doi = {10.1016/J.DISOPT.2013.10.001},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/disopt/NagarajanW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jea/NagarajanW13,
author = {Chandrashekhar Nagarajan and
David P. Williamson},
title = {An Experimental Evaluation of Incremental and Hierarchical \emph{k}-Median
Algorithms},
journal = {{ACM} J. Exp. Algorithmics},
volume = {18},
year = {2013},
url = {https://doi.org/10.1145/2543628},
doi = {10.1145/2543628},
timestamp = {Thu, 25 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jea/NagarajanW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/DvorakHW13,
author = {Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
David P. Williamson},
editor = {Hans L. Bodlaender and
Giuseppe F. Italiano},
title = {Maximizing a Submodular Function with Viability Constraints},
booktitle = {Algorithms - {ESA} 2013 - 21st Annual European Symposium, Sophia Antipolis,
France, September 2-4, 2013. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8125},
pages = {409--420},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-40450-4\_35},
doi = {10.1007/978-3-642-40450-4\_35},
timestamp = {Mon, 03 Jan 2022 22:19:39 +0100},
biburl = {https://dblp.org/rec/conf/esa/DvorakHW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/PoloczekWZ13,
author = {Matthias Poloczek and
David P. Williamson and
Anke van Zuylen},
title = {On Some Recent {MAX} {SAT} Approximation Algorithms},
journal = {CoRR},
volume = {abs/1308.3405},
year = {2013},
url = {http://arxiv.org/abs/1308.3405},
eprinttype = {arXiv},
eprint = {1308.3405},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/PoloczekWZ13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/DavisW12,
author = {James M. Davis and
David P. Williamson},
editor = {Leah Epstein and
Paolo Ferragina},
title = {A Dual-Fitting {\textdollar}{\textbackslash}frac\{3\}\{2\}{\textdollar}
-Approximation Algorithm for Some Minimum-Cost Graph Problems},
booktitle = {Algorithms - {ESA} 2012 - 20th Annual European Symposium, Ljubljana,
Slovenia, September 10-12, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7501},
pages = {373--382},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-33090-2\_33},
doi = {10.1007/978-3-642-33090-2\_33},
timestamp = {Tue, 14 May 2019 10:00:54 +0200},
biburl = {https://dblp.org/rec/conf/esa/DavisW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/latin/QianSWZ12,
author = {Jiawei Qian and
Frans Schalekamp and
David P. Williamson and
Anke van Zuylen},
editor = {David Fern{\'{a}}ndez{-}Baca},
title = {On the Integrality Gap of the Subtour {LP} for the 1, 2-TSP},
booktitle = {{LATIN} 2012: Theoretical Informatics - 10th Latin American Symposium,
Arequipa, Peru, April 16-20, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7256},
pages = {606--617},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-29344-3\_51},
doi = {10.1007/978-3-642-29344-3\_51},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/latin/QianSWZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/SchalekampWZ12,
author = {Frans Schalekamp and
David P. Williamson and
Anke van Zuylen},
editor = {Yuval Rabani},
title = {A proof of the Boyd-Carr conjecture},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {1477--1486},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.117},
doi = {10.1137/1.9781611973099.117},
timestamp = {Tue, 02 Feb 2021 17:07:31 +0100},
biburl = {https://dblp.org/rec/conf/soda/SchalekampWZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@book{DBLP:books/daglib/0030297,
author = {David P. Williamson and
David B. Shmoys},
title = {The Design of Approximation Algorithms},
publisher = {Cambridge University Press},
year = {2011},
url = {http://www.cambridge.org/de/knowledge/isbn/item5759340/?site\_locale=de\_DE},
isbn = {978-0-521-19527-0},
timestamp = {Wed, 09 Jan 2013 00:00:00 +0100},
biburl = {https://dblp.org/rec/books/daglib/0030297.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/SkutellaW11,
author = {Martin Skutella and
David P. Williamson},
title = {A note on the generalized min-sum set cover problem},
journal = {Oper. Res. Lett.},
volume = {39},
number = {6},
pages = {433--436},
year = {2011},
url = {https://doi.org/10.1016/j.orl.2011.08.002},
doi = {10.1016/J.ORL.2011.08.002},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/orl/SkutellaW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colognetwente/ZuylenSW11,
author = {Anke van Zuylen and
Frans Schalekamp and
David P. Williamson},
editor = {Ludovica Adacher and
Marta Flamini and
Gianmaria Leo and
Gaia Nicosia and
Andrea Pacifici and
Veronica Piccialli},
title = {Popular Ranking},
booktitle = {Proceedings of the 10th Cologne-Twente Workshop on graphs and combinatorial
optimization. Extended Abstracts, Villa Mondragone, Frascati, Italy,
June 14-16, 2011},
pages = {267--270},
year = {2011},
url = {http://ctw2011.dia.uniroma3.it/ctw\_proceedings.pdf\#page=279},
timestamp = {Thu, 12 Mar 2020 11:34:41 +0100},
biburl = {https://dblp.org/rec/conf/colognetwente/ZuylenSW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/QianW11,
author = {Jiawei Qian and
David P. Williamson},
editor = {Luca Aceto and
Monika Henzinger and
Jir{\'{\i}} Sgall},
title = {An \emph{O}(log\emph{n})-Competitive Algorithm for Online Constrained
Forest Problems},
booktitle = {Automata, Languages and Programming - 38th International Colloquium,
{ICALP} 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6755},
pages = {37--48},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22006-7\_4},
doi = {10.1007/978-3-642-22006-7\_4},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/QianW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wea/NagarajanW11,
author = {Chandrashekhar Nagarajan and
David P. Williamson},
editor = {Panos M. Pardalos and
Steffen Rebennack},
title = {An Experimental Evaluation of Incremental and Hierarchical \emph{k}-Median
Algorithms},
booktitle = {Experimental Algorithms - 10th International Symposium, {SEA} 2011,
Kolimpari, Chania, Crete, Greece, May 5-7, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6630},
pages = {169--180},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-20662-7\_15},
doi = {10.1007/978-3-642-20662-7\_15},
timestamp = {Mon, 05 Feb 2024 20:31:36 +0100},
biburl = {https://dblp.org/rec/conf/wea/NagarajanW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1107-1628,
author = {Frans Schalekamp and
David P. Williamson and
Anke van Zuylen},
title = {A Proof of the Boyd-Carr Conjecture},
journal = {CoRR},
volume = {abs/1107.1628},
year = {2011},
url = {http://arxiv.org/abs/1107.1628},
eprinttype = {arXiv},
eprint = {1107.1628},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1107-1628.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1107-1630,
author = {Jiawei Qian and
Frans Schalekamp and
David P. Williamson and
Anke van Zuylen},
title = {On the Integrality Gap of the Subtour {LP} for the 1,2-TSP},
journal = {CoRR},
volume = {abs/1107.1630},
year = {2011},
url = {http://arxiv.org/abs/1107.1630},
eprinttype = {arXiv},
eprint = {1107.1630},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1107-1630.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1107-2033,
author = {Martin Skutella and
David P. Williamson},
title = {A note on the generalized min-sum set cover problem},
journal = {CoRR},
volume = {abs/1107.2033},
year = {2011},
url = {http://arxiv.org/abs/1107.2033},
eprinttype = {arXiv},
eprint = {1107.2033},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1107-2033.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/LinNRW10,
author = {Guolong Lin and
Chandrashekhar Nagarajan and
Rajmohan Rajaraman and
David P. Williamson},
title = {A General Approach for Incremental Approximation and Hierarchical
Clustering},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {8},
pages = {3633--3669},
year = {2010},
url = {https://doi.org/10.1137/070698257},
doi = {10.1137/070698257},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/LinNRW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/geb/SharmaW09,
author = {Yogeshwer Sharma and
David P. Williamson},
title = {Stackelberg thresholds in network routing games or the value of altruism},
journal = {Games Econ. Behav.},
volume = {67},
number = {1},
pages = {174--190},
year = {2009},
url = {https://doi.org/10.1016/j.geb.2009.06.006},
doi = {10.1016/J.GEB.2009.06.006},
timestamp = {Sat, 22 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/geb/SharmaW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mor/ZuylenW09,
author = {Anke van Zuylen and
David P. Williamson},
title = {Deterministic Pivoting Algorithms for Constrained Ranking and Clustering
Problems},
journal = {Math. Oper. Res.},
volume = {34},
number = {3},
pages = {594--620},
year = {2009},
url = {https://doi.org/10.1287/moor.1090.0385},
doi = {10.1287/MOOR.1090.0385},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mor/ZuylenW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/RestrepoW09,
author = {Mateo Restrepo and
David P. Williamson},
title = {A simple GAP-canceling algorithm for the generalized maximum flow
problem},
journal = {Math. Program.},
volume = {118},
number = {1},
pages = {47--74},
year = {2009},
url = {https://doi.org/10.1007/s10107-007-0183-8},
doi = {10.1007/S10107-007-0183-8},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mp/RestrepoW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/networks/GabowGTW09,
author = {Harold N. Gabow and
Michel X. Goemans and
{\'{E}}va Tardos and
David P. Williamson},
title = {Approximating the smallest \emph{k}-edge connected spanning subgraph
by LP-rounding},
journal = {Networks},
volume = {53},
number = {4},
pages = {345--357},
year = {2009},
url = {https://doi.org/10.1002/net.20289},
doi = {10.1002/NET.20289},
timestamp = {Fri, 25 Dec 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/networks/GabowGTW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ArcherLW08,
author = {Aaron Archer and
Asaf Levin and
David P. Williamson},
title = {A Faster, Better Approximation Algorithm for the Minimum Latency Problem},
journal = {{SIAM} J. Comput.},
volume = {37},
number = {5},
pages = {1472--1498},
year = {2008},
url = {https://doi.org/10.1137/07068151X},
doi = {10.1137/07068151X},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ArcherLW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/NagarajanW08,
author = {Chandrashekhar Nagarajan and
David P. Williamson},
editor = {Andrea Lodi and
Alessandro Panconesi and
Giovanni Rinaldi},
title = {Offline and Online Facility Leasing},
booktitle = {Integer Programming and Combinatorial Optimization, 13th International
Conference, {IPCO} 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5035},
pages = {303--315},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-68891-4\_21},
doi = {10.1007/978-3-540-68891-4\_21},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/ipco/NagarajanW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/waoa/NagarajanSW08,
author = {Chandrashekhar Nagarajan and
Yogeshwer Sharma and
David P. Williamson},
editor = {Evripidis Bampis and
Martin Skutella},
title = {Approximation Algorithms for Prize-Collecting Network Design Problems
with General Connectivity Requirements},
booktitle = {Approximation and Online Algorithms, 6th International Workshop, {WAOA}
2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers},
series = {Lecture Notes in Computer Science},
volume = {5426},
pages = {174--187},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-93980-1\_14},
doi = {10.1007/978-3-540-93980-1\_14},
timestamp = {Thu, 23 Sep 2021 11:48:40 +0200},
biburl = {https://dblp.org/rec/conf/waoa/NagarajanSW08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/WilliamsonZ07,
author = {David P. Williamson and
Anke van Zuylen},
title = {A simpler and better derandomization of an approximation algorithm
for single source rent-or-buy},
journal = {Oper. Res. Lett.},
volume = {35},
number = {6},
pages = {707--712},
year = {2007},
url = {https://doi.org/10.1016/j.orl.2007.02.005},
doi = {10.1016/J.ORL.2007.02.005},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/orl/WilliamsonZ07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sigecom/SharmaW07,
author = {Yogeshwer Sharma and
David P. Williamson},
editor = {Jeffrey K. MacKie{-}Mason and
David C. Parkes and
Paul Resnick},
title = {Stackelberg thresholds in network routing games or the value of altruism},
booktitle = {Proceedings 8th {ACM} Conference on Electronic Commerce (EC-2007),
San Diego, California, USA, June 11-15, 2007},
pages = {93--102},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250910.1250925},
doi = {10.1145/1250910.1250925},
timestamp = {Tue, 27 Nov 2018 11:56:48 +0100},
biburl = {https://dblp.org/rec/conf/sigecom/SharmaW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ZuylenHJW07,
author = {Anke van Zuylen and
Rajneesh Hegde and
Kamal Jain and
David P. Williamson},
editor = {Nikhil Bansal and
Kirk Pruhs and
Clifford Stein},
title = {Deterministic pivoting algorithms for constrained ranking and clustering
problems},
booktitle = {Proceedings of the Eighteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2007, New Orleans, Louisiana, USA, January 7-9,
2007},
pages = {405--414},
publisher = {{SIAM}},
year = {2007},
url = {http://dl.acm.org/citation.cfm?id=1283383.1283426},
timestamp = {Tue, 15 Feb 2022 07:54:27 +0100},
biburl = {https://dblp.org/rec/conf/soda/ZuylenHJW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/SharmaSW07,
author = {Yogeshwer Sharma and
Chaitanya Swamy and
David P. Williamson},
editor = {Nikhil Bansal and
Kirk Pruhs and
Clifford Stein},
title = {Approximation algorithms for prize collecting forest problems with
submodular penalty functions},
booktitle = {Proceedings of the Eighteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2007, New Orleans, Louisiana, USA, January 7-9,
2007},
pages = {1275--1284},
publisher = {{SIAM}},
year = {2007},
url = {http://dl.acm.org/citation.cfm?id=1283383.1283520},
timestamp = {Fri, 07 Dec 2012 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/SharmaSW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/waoa/ZuylenW07,
author = {Anke van Zuylen and
David P. Williamson},
editor = {Christos Kaklamanis and
Martin Skutella},
title = {Deterministic Algorithms for Rank Aggregation and Other Ranking and
Clustering Problems},
booktitle = {Approximation and Online Algorithms, 5th International Workshop, {WAOA}
2007, Eilat, Israel, October 11-12, 2007. Revised Papers},
series = {Lecture Notes in Computer Science},
volume = {4927},
pages = {260--273},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-77918-6\_21},
doi = {10.1007/978-3-540-77918-6\_21},
timestamp = {Tue, 14 May 2019 10:00:46 +0200},
biburl = {https://dblp.org/rec/conf/waoa/ZuylenW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/ipco/2007,
editor = {Matteo Fischetti and
David P. Williamson},
title = {Integer Programming and Combinatorial Optimization, 12th International
{IPCO} Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4513},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-72792-7},
doi = {10.1007/978-3-540-72792-7},
isbn = {978-3-540-72791-0},
timestamp = {Tue, 14 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/ipco/2007.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/FleischerJW06,
author = {Lisa Fleischer and
Kamal Jain and
David P. Williamson},
title = {Iterative rounding 2-approximation algorithms for minimum-cost vertex
connectivity problems},
journal = {J. Comput. Syst. Sci.},
volume = {72},
number = {5},
pages = {838--867},
year = {2006},
url = {https://doi.org/10.1016/j.jcss.2005.05.006},
doi = {10.1016/J.JCSS.2005.05.006},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/FleischerJW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/UmaWW06,
author = {R. N. Uma and
Joel Wein and
David P. Williamson},
title = {On the relationship between combinatorial and LP-based lower bounds
for NP-hard scheduling problems},
journal = {Theor. Comput. Sci.},
volume = {361},
number = {2-3},
pages = {241--256},
year = {2006},
url = {https://doi.org/10.1016/j.tcs.2006.05.013},
doi = {10.1016/J.TCS.2006.05.013},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/UmaWW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sigecom/RusmevichientongW06,
author = {Paat Rusmevichientong and
David P. Williamson},
editor = {Joan Feigenbaum and
John C.{-}I. Chuang and
David M. Pennock},
title = {An adaptive algorithm for selecting profitable keywords for search-based
advertising services},
booktitle = {Proceedings 7th {ACM} Conference on Electronic Commerce (EC-2006),
Ann Arbor, Michigan, USA, June 11-15, 2006},
pages = {260--269},
publisher = {{ACM}},
year = {2006},
url = {https://doi.org/10.1145/1134707.1134736},
doi = {10.1145/1134707.1134736},
timestamp = {Tue, 27 Nov 2018 11:56:48 +0100},
biburl = {https://dblp.org/rec/conf/sigecom/RusmevichientongW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/RestrepoW06,
author = {Mateo Restrepo and
David P. Williamson},
title = {A simple GAP-canceling algorithm for the generalized maximum flow
problem},
booktitle = {Proceedings of the Seventeenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2006, Miami, Florida, USA, January 22-26, 2006},
pages = {534--543},
publisher = {{ACM} Press},
year = {2006},
url = {http://dl.acm.org/citation.cfm?id=1109557.1109616},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/RestrepoW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/LinNRW06,
author = {Guolong Lin and
Chandrashekhar Nagarajan and
Rajmohan Rajaraman and
David P. Williamson},
title = {A general approach for incremental approximation and hierarchical
clustering},
booktitle = {Proceedings of the Seventeenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2006, Miami, Florida, USA, January 22-26, 2006},
pages = {1147--1156},
publisher = {{ACM} Press},
year = {2006},
url = {http://dl.acm.org/citation.cfm?id=1109557.1109684},
timestamp = {Fri, 07 Dec 2012 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/LinNRW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/ChudakW05,
author = {Fabi{\'{a}}n A. Chudak and
David P. Williamson},
title = {Improved approximation algorithms for capacitated facility location
problems},
journal = {Math. Program.},
volume = {102},
number = {2},
pages = {207--222},
year = {2005},
url = {https://doi.org/10.1007/s10107-004-0524-9},
doi = {10.1007/S10107-004-0524-9},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mp/ChudakW05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GabowGTW05,
author = {Harold N. Gabow and
Michel X. Goemans and
{\'{E}}va Tardos and
David P. Williamson},
title = {Approximating the smallest \emph{k}-edge connected spanning subgraph
by LP-rounding},
booktitle = {Proceedings of the Sixteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2005, Vancouver, British Columbia, Canada, January
23-25, 2005},
pages = {562--571},
publisher = {{SIAM}},
year = {2005},
url = {http://dl.acm.org/citation.cfm?id=1070432.1070511},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/GabowGTW05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/GoemansW04,
author = {Michel X. Goemans and
David P. Williamson},
title = {Approximation algorithms for M\({}_{\mbox{AX}}\)-3-C\({}_{\mbox{UT}}\)
and other problems via complex semidefinite programming},
journal = {J. Comput. Syst. Sci.},
volume = {68},
number = {2},
pages = {442--470},
year = {2004},
url = {https://doi.org/10.1016/j.jcss.2003.07.012},
doi = {10.1016/J.JCSS.2003.07.012},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/GoemansW04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/ChudakRW04,
author = {Fabi{\'{a}}n A. Chudak and
Tim Roughgarden and
David P. Williamson},
title = {Approximate \emph{k}-MSTs and \emph{k}-Steiner trees via the primal-dual
method and Lagrangean relaxation},
journal = {Math. Program.},
volume = {100},
number = {2},
pages = {411--421},
year = {2004},
url = {https://doi.org/10.1007/s10107-003-0479-2},
doi = {10.1007/S10107-003-0479-2},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mp/ChudakRW04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ArcherW03,
author = {Aaron Archer and
David P. Williamson},
title = {Faster approximation algorithms for the minimum latency problem},
booktitle = {Proceedings of the Fourteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, January 12-14, 2003, Baltimore, Maryland, {USA}},
pages = {88--96},
publisher = {{ACM/SIAM}},
year = {2003},
url = {http://dl.acm.org/citation.cfm?id=644108.644122},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/ArcherW03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/www/FaginKMNSTW03,
author = {Ronald Fagin and
Ravi Kumar and
Kevin S. McCurley and
Jasmine Novak and
D. Sivakumar and
John A. Tomlin and
David P. Williamson},
editor = {Guszt{\'{a}}v Hencsey and
Bebo White and
Yih{-}Farn Robin Chen and
L{\'{a}}szl{\'{o}} Kov{\'{a}}cs and
Steve Lawrence},
title = {Searching the workplace web},
booktitle = {Proceedings of the Twelfth International World Wide Web Conference,
{WWW} 2003, Budapest, Hungary, May 20-24, 2003},
pages = {366--375},
publisher = {{ACM}},
year = {2003},
url = {https://doi.org/10.1145/775152.775204},
doi = {10.1145/775152.775204},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/www/FaginKMNSTW03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/RaviW02,
author = {R. Ravi and
David P. Williamson},
title = {Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity
Problems},
journal = {Algorithmica},
volume = {34},
number = {1},
pages = {98--107},
year = {2002},
url = {https://doi.org/10.1007/s00453-002-0970-9},
doi = {10.1007/S00453-002-0970-9},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/RaviW02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jal/AsanoW02,
author = {Takao Asano and
David P. Williamson},
title = {Improved Approximation Algorithms for {MAX} {SAT}},
journal = {J. Algorithms},
volume = {42},
number = {1},
pages = {173--202},
year = {2002},
url = {https://doi.org/10.1006/jagm.2001.1202},
doi = {10.1006/JAGM.2001.1202},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/AsanoW02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jal/JainMVW02,
author = {Kamal Jain and
Ion I. Mandoiu and
Vijay V. Vazirani and
David P. Williamson},
title = {A primal-dual schema based approximation algorithm for the element
connectivity problem},
journal = {J. Algorithms},
volume = {45},
number = {1},
pages = {1--15},
year = {2002},
url = {https://doi.org/10.1016/S0196-6774(02)00222-5},
doi = {10.1016/S0196-6774(02)00222-5},
timestamp = {Tue, 06 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/JainMVW02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/Williamson02,
author = {David P. Williamson},
title = {The primal-dual method for approximation algorithms},
journal = {Math. Program.},
volume = {91},
number = {3},
pages = {447--478},
year = {2002},
url = {https://doi.org/10.1007/s101070100262},
doi = {10.1007/S101070100262},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mp/Williamson02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/RaviW02,
author = {R. Ravi and
David P. Williamson},
editor = {David Eppstein},
title = {Erratum: an approximation algorithm for minimum-cost vertex-connectivity
problems},
booktitle = {Proceedings of the Thirteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, January 6-8, 2002, San Francisco, CA, {USA}},
pages = {1000--1001},
publisher = {{ACM/SIAM}},
year = {2002},
url = {http://dl.acm.org/citation.cfm?id=545381.545510},
timestamp = {Mon, 31 Aug 2015 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/RaviW02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/BorodinKRSW01,
author = {Allan Borodin and
Jon M. Kleinberg and
Prabhakar Raghavan and
Madhu Sudan and
David P. Williamson},
title = {Adversarial queuing theory},
journal = {J. {ACM}},
volume = {48},
number = {1},
pages = {13--38},
year = {2001},
url = {https://doi.org/10.1145/363647.363659},
doi = {10.1145/363647.363659},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/BorodinKRSW01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FleischerJW01,
author = {Lisa Fleischer and
Kamal Jain and
David P. Williamson},
title = {An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity
Problem},
booktitle = {42nd Annual Symposium on Foundations of Computer Science, {FOCS} 2001,
14-17 October 2001, Las Vegas, Nevada, {USA}},
pages = {339--347},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/SFCS.2001.959908},
doi = {10.1109/SFCS.2001.959908},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/FleischerJW01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/ChudakRW01,
author = {Fabi{\'{a}}n A. Chudak and
Tim Roughgarden and
David P. Williamson},
editor = {Karen I. Aardal and
Bert Gerards},
title = {Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method
and Lagrangean Relaxation},
booktitle = {Integer Programming and Combinatorial Optimization, 8th International
{IPCO} Conference, Utrecht, The Netherlands, June 13-15, 2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2081},
pages = {60--70},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-45535-3\_5},
doi = {10.1007/3-540-45535-3\_5},
timestamp = {Tue, 25 Jul 2023 13:14:28 +0200},
biburl = {https://dblp.org/rec/conf/ipco/ChudakRW01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoemansW01,
author = {Michel X. Goemans and
David P. Williamson},
editor = {Jeffrey Scott Vitter and
Paul G. Spirakis and
Mihalis Yannakakis},
title = {Approximation algorithms for {MAX-3-CUT} and other problems via complex
semidefinite programming},
booktitle = {Proceedings on 33rd Annual {ACM} Symposium on Theory of Computing,
July 6-8, 2001, Heraklion, Crete, Greece},
pages = {443--452},
publisher = {{ACM}},
year = {2001},
url = {https://doi.org/10.1145/380752.380838},
doi = {10.1145/380752.380838},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GoemansW01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/GoemansWW00,
author = {Michel X. Goemans and
Joel Wein and
David P. Williamson},
title = {A 1.47-approximation algorithm for a preemptive single-machine scheduling
problem},
journal = {Oper. Res. Lett.},
volume = {26},
number = {4},
pages = {149--154},
year = {2000},
url = {https://doi.org/10.1016/S0167-6377(00)00024-9},
doi = {10.1016/S0167-6377(00)00024-9},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/orl/GoemansWW00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/AggarwalKW00,
author = {Alok Aggarwal and
Jon M. Kleinberg and
David P. Williamson},
title = {Node-Disjoint Paths on the Mesh and a New Trade-Off in {VLSI} Layout},
journal = {{SIAM} J. Comput.},
volume = {29},
number = {4},
pages = {1321--1333},
year = {2000},
url = {https://doi.org/10.1137/S0097539796312733},
doi = {10.1137/S0097539796312733},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/AggarwalKW00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/TrevisanSSW00,
author = {Luca Trevisan and
Gregory B. Sorkin and
Madhu Sudan and
David P. Williamson},
title = {Gadgets, Approximation, and Linear Programming},
journal = {{SIAM} J. Comput.},
volume = {29},
number = {6},
pages = {2074--2097},
year = {2000},
url = {https://doi.org/10.1137/S0097539797328847},
doi = {10.1137/S0097539797328847},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/TrevisanSSW00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KhannaSTW00,
author = {Sanjeev Khanna and
Madhu Sudan and
Luca Trevisan and
David P. Williamson},
title = {The Approximability of Constraint Satisfaction Problems},
journal = {{SIAM} J. Comput.},
volume = {30},
number = {6},
pages = {1863--1920},
year = {2000},
url = {https://doi.org/10.1137/S0097539799349948},
doi = {10.1137/S0097539799349948},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KhannaSTW00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamdm/GoemansW00,
author = {Michel X. Goemans and
David P. Williamson},
title = {Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler},
journal = {{SIAM} J. Discret. Math.},
volume = {13},
number = {3},
pages = {281--294},
year = {2000},
url = {https://doi.org/10.1137/S0895480197330254},
doi = {10.1137/S0895480197330254},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/GoemansW00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AsanoW00,
author = {Takao Asano and
David P. Williamson},
editor = {David B. Shmoys},
title = {Improved approximation algorithms for {MAX} {SAT}},
booktitle = {Proceedings of the Eleventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, January 9-11, 2000, San Francisco, CA, {USA}},
pages = {96--105},
publisher = {{ACM/SIAM}},
year = {2000},
url = {http://dl.acm.org/citation.cfm?id=338219.338240},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/AsanoW00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/ChudakW99,
author = {Fabi{\'{a}}n A. Chudak and
David P. Williamson},
editor = {G{\'{e}}rard Cornu{\'{e}}jols and
Rainer E. Burkard and
Gerhard J. Woeginger},
title = {Improved Approximation Algorithms for Capacitated Facility Location
Problems},
booktitle = {Integer Programming and Combinatorial Optimization, 7th International
{IPCO} Conference, Graz, Austria, June 9-11, 1999, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1610},
pages = {99--113},
publisher = {Springer},
year = {1999},
url = {https://doi.org/10.1007/3-540-48777-8\_8},
doi = {10.1007/3-540-48777-8\_8},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/ipco/ChudakW99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GoemansW99,
author = {Michel X. Goemans and
David P. Williamson},
editor = {Robert Endre Tarjan and
Tandy J. Warnow},
title = {Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler},
booktitle = {Proceedings of the Tenth Annual {ACM-SIAM} Symposium on Discrete Algorithms,
17-19 January 1999, Baltimore, Maryland, {USA}},
pages = {366--375},
publisher = {{ACM/SIAM}},
year = {1999},
url = {http://dl.acm.org/citation.cfm?id=314500.314589},
timestamp = {Thu, 05 Jul 2018 07:29:57 +0200},
biburl = {https://dblp.org/rec/conf/soda/GoemansW99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/JainMVW99,
author = {Kamal Jain and
Ion I. Mandoiu and
Vijay V. Vazirani and
David P. Williamson},
editor = {Robert Endre Tarjan and
Tandy J. Warnow},
title = {A Primal-Dual Schema Based Approximation Algorithm for the Element
Connectivity Problem},
booktitle = {Proceedings of the Tenth Annual {ACM-SIAM} Symposium on Discrete Algorithms,
17-19 January 1999, Baltimore, Maryland, {USA}},
pages = {484--489},
publisher = {{ACM/SIAM}},
year = {1999},
url = {http://dl.acm.org/citation.cfm?id=314500.314869},
timestamp = {Fri, 07 Dec 2012 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/JainMVW99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorica/GoemansW98,
author = {Michel X. Goemans and
David P. Williamson},
title = {Primal-Dual Approximation Algorithms for Feedback Problems in Planar
Graphs},
journal = {Comb.},
volume = {18},
number = {1},
pages = {37--59},
year = {1998},
url = {https://doi.org/10.1007/PL00009810},
doi = {10.1007/PL00009810},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/combinatorica/GoemansW98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/GabowGW98,
author = {Harold N. Gabow and
Michel X. Goemans and
David P. Williamson},
title = {An efficient approximation algorithm for the survivable network design
problem},
journal = {Math. Program.},
volume = {82},
pages = {13--40},
year = {1998},
url = {https://doi.org/10.1007/BF01585864},
doi = {10.1007/BF01585864},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mp/GabowGW98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/ChudakGHW98,
author = {Fabi{\'{a}}n A. Chudak and
Michel X. Goemans and
Dorit S. Hochbaum and
David P. Williamson},
title = {A primal-dual interpretation of two 2-approximation algorithms for
the feedback vertex set problem in undirected graphs},
journal = {Oper. Res. Lett.},
volume = {22},
number = {4-5},
pages = {111--118},
year = {1998},
url = {https://doi.org/10.1016/S0167-6377(98)00021-2},
doi = {10.1016/S0167-6377(98)00021-2},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/orl/ChudakGHW98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/RaviW97,
author = {R. Ravi and
David P. Williamson},
title = {An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems},
journal = {Algorithmica},
volume = {18},
number = {1},
pages = {21--43},
year = {1997},
url = {https://doi.org/10.1007/BF02523686},
doi = {10.1007/BF02523686},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/RaviW97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ior/WilliamsonHHHLS97,
author = {David P. Williamson and
Leslie A. Hall and
J. A. Hoogeveen and
Cor A. J. Hurkens and
Jan Karel Lenstra and
Sergey Vasil'evich Sevast'janov and
David B. Shmoys},
title = {Short Shop Schedules},
journal = {Oper. Res.},
volume = {45},
number = {2},
pages = {288--294},
year = {1997},
url = {https://doi.org/10.1287/opre.45.2.288},
doi = {10.1287/OPRE.45.2.288},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ior/WilliamsonHHHLS97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KhannaSW97,
author = {Sanjeev Khanna and
Madhu Sudan and
David P. Williamson},
editor = {Frank Thomson Leighton and
Peter W. Shor},
title = {A Complete Classification of the Approximability of Maximization Problems
Derived from Boolean Constraint Satisfaction},
booktitle = {Proceedings of the Twenty-Ninth Annual {ACM} Symposium on the Theory
of Computing, El Paso, Texas, USA, May 4-6, 1997},
pages = {11--20},
publisher = {{ACM}},
year = {1997},
url = {https://doi.org/10.1145/258533.258538},
doi = {10.1145/258533.258538},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/KhannaSW97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wg/Williamson97,
author = {David P. Williamson},
editor = {Rolf H. M{\"{o}}hring},
title = {Gadgets, Approximation, and Linear Programming: Improved Hardness
Results for Cut and Satisfiability Problems (Abstract of Invited Lecture)},
booktitle = {Graph-Theoretic Concepts in Computer Science, 23rd International Workshop,
{WG} '97, Berlin, Germany, June 18-20, 1997, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1335},
pages = {1},
publisher = {Springer},
year = {1997},
url = {https://doi.org/10.1007/BFb0024482},
doi = {10.1007/BFB0024482},
timestamp = {Tue, 14 May 2019 10:00:40 +0200},
biburl = {https://dblp.org/rec/conf/wg/Williamson97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/informs/WilliamsonG96,
author = {David P. Williamson and
Michel X. Goemans},
title = {Computational Experience with an Approximation Algorithm on Large-Scale
Euclidean Matching Instances},
journal = {{INFORMS} J. Comput.},
volume = {8},
number = {1},
pages = {29--40},
year = {1996},
url = {https://doi.org/10.1287/ijoc.8.1.29},
doi = {10.1287/IJOC.8.1.29},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/informs/WilliamsonG96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/HenzingerW96,
author = {Monika Henzinger and
David P. Williamson},
title = {On the Number of Small Cuts in a Graph},
journal = {Inf. Process. Lett.},
volume = {59},
number = {1},
pages = {41--44},
year = {1996},
url = {https://doi.org/10.1016/0020-0190(96)00079-8},
doi = {10.1016/0020-0190(96)00079-8},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/HenzingerW96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/TrevisanSSW96,
author = {Luca Trevisan and
Gregory B. Sorkin and
Madhu Sudan and
David P. Williamson},
title = {Gadgets, Approximation, and Linear Programming (extended abstract)},
booktitle = {37th Annual Symposium on Foundations of Computer Science, {FOCS} '96,
Burlington, Vermont, USA, 14-16 October, 1996},
pages = {617--626},
publisher = {{IEEE} Computer Society},
year = {1996},
url = {https://doi.org/10.1109/SFCS.1996.548521},
doi = {10.1109/SFCS.1996.548521},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/TrevisanSSW96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/GoemansW96,
author = {Michel X. Goemans and
David P. Williamson},
editor = {William H. Cunningham and
S. Thomas McCormick and
Maurice Queyranne},
title = {Primal-Dual Approximation Algorithms for Feedback Problems},
booktitle = {Integer Programming and Combinatorial Optimization, 5th International
{IPCO} Conference, Vancouver, British Columbia, Canada, June 3-5,
1996, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1084},
pages = {147--161},
publisher = {Springer},
year = {1996},
url = {https://doi.org/10.1007/3-540-61310-2\_12},
doi = {10.1007/3-540-61310-2\_12},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/ipco/GoemansW96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BorodinKRSW96,
author = {Allan Borodin and
Jon M. Kleinberg and
Prabhakar Raghavan and
Madhu Sudan and
David P. Williamson},
editor = {Gary L. Miller},
title = {Adversarial Queueing Theory},
booktitle = {Proceedings of the Twenty-Eighth Annual {ACM} Symposium on the Theory
of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996},
pages = {376--385},
publisher = {{ACM}},
year = {1996},
url = {https://doi.org/10.1145/237814.237984},
doi = {10.1145/237814.237984},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BorodinKRSW96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AggarwalKW96,
author = {Alok Aggarwal and
Jon M. Kleinberg and
David P. Williamson},
editor = {Gary L. Miller},
title = {Node-Disjoint Paths on the Mesh and a New Trade-Off in {VLSI} Layout},
booktitle = {Proceedings of the Twenty-Eighth Annual {ACM} Symposium on the Theory
of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996},
pages = {585--594},
publisher = {{ACM}},
year = {1996},
url = {https://doi.org/10.1145/237814.238007},
doi = {10.1145/237814.238007},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AggarwalKW96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR96-062,
author = {Sanjeev Khanna and
Madhu Sudan and
David P. Williamson},
title = {A Complete Characterization of the Approximability of Maximization
Problems Derived from Boolean Constraint Satisfaction},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR96-062}},
year = {1996},
url = {https://eccc.weizmann.ac.il/eccc-reports/1996/TR96-062/index.html},
eprinttype = {ECCC},
eprint = {TR96-062},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR96-062.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorica/WilliamsonGMV95,
author = {David P. Williamson and
Michel X. Goemans and
Milena Mihail and
Vijay V. Vazirani},
title = {A Primal-Dual Approximation Algorithm for Generalized Steiner Network
Problems},
journal = {Comb.},
volume = {15},
number = {3},
pages = {435--454},
year = {1995},
url = {https://doi.org/10.1007/BF01299747},
doi = {10.1007/BF01299747},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/combinatorica/WilliamsonGMV95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/GoemansW95,
author = {Michel X. Goemans and
David P. Williamson},
title = {Improved Approximation Algorithms for Maximum Cut and Satisfiability
Problems Using Semidefinite Programming},
journal = {J. {ACM}},
volume = {42},
number = {6},
pages = {1115--1145},
year = {1995},
url = {https://doi.org/10.1145/227683.227684},
doi = {10.1145/227683.227684},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/GoemansW95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GoemansW95,
author = {Michel X. Goemans and
David P. Williamson},
title = {A General Approximation Technique for Constrained Forest Problems},
journal = {{SIAM} J. Comput.},
volume = {24},
number = {2},
pages = {296--317},
year = {1995},
url = {https://doi.org/10.1137/S0097539793242618},
doi = {10.1137/S0097539793242618},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/GoemansW95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ShmoysWW95,
author = {David B. Shmoys and
Joel Wein and
David P. Williamson},
title = {Scheduling Parallel Machines On-Line},
journal = {{SIAM} J. Comput.},
volume = {24},
number = {6},
pages = {1313--1331},
year = {1995},
url = {https://doi.org/10.1137/S0097539793248317},
doi = {10.1137/S0097539793248317},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ShmoysWW95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/GoemansW94,
author = {Michel X. Goemans and
David P. Williamson},
title = {Approximating minimum-cost graph problems with spanning tree edges},
journal = {Oper. Res. Lett.},
volume = {16},
number = {4},
pages = {183--189},
year = {1994},
url = {https://doi.org/10.1016/0167-6377(94)90067-1},
doi = {10.1016/0167-6377(94)90067-1},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/orl/GoemansW94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamdm/GoemansW94,
author = {Michel X. Goemans and
David P. Williamson},
title = {New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem},
journal = {{SIAM} J. Discret. Math.},
volume = {7},
number = {4},
pages = {656--666},
year = {1994},
url = {https://doi.org/10.1137/S0895480192243516},
doi = {10.1137/S0895480192243516},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/GoemansW94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GoemansGPSTW94,
author = {Michel X. Goemans and
Andrew V. Goldberg and
Serge A. Plotkin and
David B. Shmoys and
{\'{E}}va Tardos and
David P. Williamson},
editor = {Daniel Dominic Sleator},
title = {Improved Approximation Algorithms for Network Design Problems},
booktitle = {Proceedings of the Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms.
23-25 January 1994, Arlington, Virginia, {USA}},
pages = {223--232},
publisher = {{ACM/SIAM}},
year = {1994},
url = {http://dl.acm.org/citation.cfm?id=314464.314497},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/GoemansGPSTW94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/WilliamsonG94,
author = {David P. Williamson and
Michel X. Goemans},
editor = {Daniel Dominic Sleator},
title = {Computational Experience with an Approximation Algorithm on Large-Scale
Euclidean Matching Instances},
booktitle = {Proceedings of the Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms.
23-25 January 1994, Arlington, Virginia, {USA}},
pages = {355--364},
publisher = {{ACM/SIAM}},
year = {1994},
url = {http://dl.acm.org/citation.cfm?id=314464.314568},
timestamp = {Fri, 07 Dec 2012 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/WilliamsonG94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoemansW94,
author = {Michel X. Goemans and
David P. Williamson},
editor = {Frank Thomson Leighton and
Michael T. Goodrich},
title = {.879-approximation algorithms for {MAX} {CUT} and {MAX} 2SAT},
booktitle = {Proceedings of the Twenty-Sixth Annual {ACM} Symposium on Theory of
Computing, 23-25 May 1994, Montr{\'{e}}al, Qu{\'{e}}bec,
Canada},
pages = {422--431},
publisher = {{ACM}},
year = {1994},
url = {https://doi.org/10.1145/195058.195216},
doi = {10.1145/195058.195216},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GoemansW94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/BienstockGSW93,
author = {Daniel Bienstock and
Michel X. Goemans and
David Simchi{-}Levi and
David P. Williamson},
title = {A note on the prize collecting traveling salesman problem},
journal = {Math. Program.},
volume = {59},
pages = {413--420},
year = {1993},
url = {https://doi.org/10.1007/BF01581256},
doi = {10.1007/BF01581256},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mp/BienstockGSW93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/GabowGW93,
author = {Harold N. Gabow and
Michel X. Goemans and
David P. Williamson},
editor = {Giovanni Rinaldi and
Laurence A. Wolsey},
title = {An efficient approximation algorithm for the survivable network design
problem},
booktitle = {Proceedings of the 3rd Integer Programming and Combinatorial Optimization
Conference, Erice, Italy, April 29 - May 1, 1993},
pages = {57--74},
publisher = {{CIACO}},
year = {1993},
timestamp = {Wed, 09 Oct 2002 11:26:33 +0200},
biburl = {https://dblp.org/rec/conf/ipco/GabowGW93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/GoemansW93,
author = {Michel X. Goemans and
David P. Williamson},
editor = {Giovanni Rinaldi and
Laurence A. Wolsey},
title = {A new {\textbackslash}frac34-approximation algorithm for {MAX} {SAT}},
booktitle = {Proceedings of the 3rd Integer Programming and Combinatorial Optimization
Conference, Erice, Italy, April 29 - May 1, 1993},
pages = {313--321},
publisher = {{CIACO}},
year = {1993},
timestamp = {Wed, 09 Oct 2002 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/ipco/GoemansW93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/WilliamsonGMV93,
author = {David P. Williamson and
Michel X. Goemans and
Milena Mihail and
Vijay V. Vazirani},
editor = {S. Rao Kosaraju and
David S. Johnson and
Alok Aggarwal},
title = {A primal-dual approximation algorithm for generalized Steiner network
problems},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM} Symposium on Theory of
Computing, May 16-18, 1993, San Diego, CA, {USA}},
pages = {708--717},
publisher = {{ACM}},
year = {1993},
url = {https://doi.org/10.1145/167088.167268},
doi = {10.1145/167088.167268},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/WilliamsonGMV93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/Williamson92,
author = {David P. Williamson},
title = {Analysis of the Held-Karp lower bound for the asymmetric {TSP}},
journal = {Oper. Res. Lett.},
volume = {12},
number = {2},
pages = {83--88},
year = {1992},
url = {https://doi.org/10.1016/0167-6377(92)90068-E},
doi = {10.1016/0167-6377(92)90068-E},
timestamp = {Thu, 23 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/orl/Williamson92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GoemansW92,
author = {Michel X. Goemans and
David P. Williamson},
editor = {Greg N. Frederickson},
title = {A General Approximation Technique for Constrained Forest Problems},
booktitle = {Proceedings of the Third Annual {ACM/SIGACT-SIAM} Symposium on Discrete
Algorithms, 27-29 January 1992, Orlando, Florida, {USA}},
pages = {307--316},
publisher = {{ACM/SIAM}},
year = {1992},
url = {http://dl.acm.org/citation.cfm?id=139404.139468},
timestamp = {Thu, 05 Jul 2018 07:29:02 +0200},
biburl = {https://dblp.org/rec/conf/soda/GoemansW92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/orl/PottsSW91,
author = {Chris N. Potts and
David B. Shmoys and
David P. Williamson},
title = {Permutation vs. non-permutation flow shop schedules},
journal = {Oper. Res. Lett.},
volume = {10},
number = {5},
pages = {281--284},
year = {1991},
url = {https://doi.org/10.1016/0167-6377(91)90014-G},
doi = {10.1016/0167-6377(91)90014-G},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/orl/PottsSW91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dimacs/ShmoysWW91,
author = {David B. Shmoys and
Joel Wein and
David P. Williamson},
editor = {Lyle A. McGeoch and
Daniel Dominic Sleator},
title = {Scheduling Parallel Machines On-line},
booktitle = {On-Line Algorithms, Proceedings of a {DIMACS} Workshop, New Brunswick,
New Jersey, USA, February 11-13, 1991},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {7},
pages = {163--166},
publisher = {{DIMACS/AMS}},
year = {1991},
url = {https://doi.org/10.1090/dimacs/007/13},
doi = {10.1090/DIMACS/007/13},
timestamp = {Mon, 22 May 2023 16:07:35 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/ShmoysWW91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ShmoysWW91,
author = {David B. Shmoys and
Joel Wein and
David P. Williamson},
title = {Scheduling Parallel Machines On-Line},
booktitle = {32nd Annual Symposium on Foundations of Computer Science, San Juan,
Puerto Rico, 1-4 October 1991},
pages = {131--140},
publisher = {{IEEE} Computer Society},
year = {1991},
url = {https://doi.org/10.1109/SFCS.1991.185361},
doi = {10.1109/SFCS.1991.185361},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ShmoysWW91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/ShmoysW90,
author = {David B. Shmoys and
David P. Williamson},
title = {Analyzing the Held-Karp {TSP} Bound: {A} Monotonicity Property with
Application},
journal = {Inf. Process. Lett.},
volume = {35},
number = {6},
pages = {281--285},
year = {1990},
url = {https://doi.org/10.1016/0020-0190(90)90028-V},
doi = {10.1016/0020-0190(90)90028-V},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/ShmoysW90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
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.
last updated on 2024-04-08 01:07 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:
