Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Daniel Dadush, Zhuan Khye Koh, Bento Natura, and László A. Végh. An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 36:1-36:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{dadush_et_al:LIPIcs.ESA.2021.36, author = {Dadush, Daniel and Koh, Zhuan Khye and Natura, Bento and V\'{e}gh, L\'{a}szl\'{o} A.}, title = {{An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {36:1--36:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.36}, URN = {urn:nbn:de:0030-drops-146172}, doi = {10.4230/LIPIcs.ESA.2021.36}, annote = {Keywords: Newton-Dinkelbach method, fractional optimization, parametric optimization, strongly polynomial algorithms, two variables per inequality systems, Markov decision processes, submodular function minimization} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Sander Borst, Daniel Dadush, Neil Olver, and Makrand Sinha. Majorizing Measures for the Optimizer. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 73:1-73:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{borst_et_al:LIPIcs.ITCS.2021.73, author = {Borst, Sander and Dadush, Daniel and Olver, Neil and Sinha, Makrand}, title = {{Majorizing Measures for the Optimizer}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {73:1--73:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.73}, URN = {urn:nbn:de:0030-drops-136120}, doi = {10.4230/LIPIcs.ITCS.2021.73}, annote = {Keywords: Majorizing measures, Generic chaining, Gaussian processes, Convex optimization, Dimensionality Reduction} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Thomas Bosman and Neil Olver. Exploring the Tractability of the Capped Hose Model. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 19:1-19:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{bosman_et_al:LIPIcs.ESA.2017.19, author = {Bosman, Thomas and Olver, Neil}, title = {{Exploring the Tractability of the Capped Hose Model}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {19:1--19:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.19}, URN = {urn:nbn:de:0030-drops-78663}, doi = {10.4230/LIPIcs.ESA.2017.19}, annote = {Keywords: robust network design, VPN problem} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy, and Jens Vygen. On the Integrality Gap of the Prize-Collecting Steiner Forest LP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 17:1-17:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{konemann_et_al:LIPIcs.APPROX-RANDOM.2017.17, author = {K\"{o}nemann, Jochen and Olver, Neil and Pashkovich, Kanstantsin and Ravi, R. and Swamy, Chaitanya and Vygen, Jens}, title = {{On the Integrality Gap of the Prize-Collecting Steiner Forest LP}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {17:1--17:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.17}, URN = {urn:nbn:de:0030-drops-75665}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.17}, annote = {Keywords: Integrality gap, Steiner tree, Steiner forest, prize-collecting, Lagrangianmultiplier- preserving} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Andreas Emil Feldmann, Jochen Könemann, Neil Olver, and Laura Sanità. On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 176-191, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{feldmann_et_al:LIPIcs.APPROX-RANDOM.2014.176, author = {Feldmann, Andreas Emil and K\"{o}nemann, Jochen and Olver, Neil and Sanit\`{a}, Laura}, title = {{On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {176--191}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.176}, URN = {urn:nbn:de:0030-drops-46962}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.176}, annote = {Keywords: Steiner tree, bidirected cut relaxation, hypergraphic relaxation, polyhedral equivalence, approximation algorithms} }
Feedback for Dagstuhl Publishing