Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo, Jarosław Byrka, Fabrizio Grandoni, Krzysztof Sornat, and Antoine Tinguely. An O(loglog n)-Approximation for Submodular Facility Location. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abbasi_et_al:LIPIcs.ICALP.2024.5, author = {Abbasi, Fateme and Adamczyk, Marek and Bosch-Calvo, Miguel and Byrka, Jaros{\l}aw and Grandoni, Fabrizio and Sornat, Krzysztof and Tinguely, Antoine}, title = {{An O(loglog n)-Approximation for Submodular Facility Location}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.5}, URN = {urn:nbn:de:0030-drops-201488}, doi = {10.4230/LIPIcs.ICALP.2024.5}, annote = {Keywords: approximation algorithms, facility location, submodular facility location, universal stochastic facility location} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Marcin Bienkowski and Guy Even. An Improved Approximation Algorithm for Dynamic Minimum Linear Arrangement. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bienkowski_et_al:LIPIcs.STACS.2024.15, author = {Bienkowski, Marcin and Even, Guy}, title = {{An Improved Approximation Algorithm for Dynamic Minimum Linear Arrangement}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {15:1--15:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.15}, URN = {urn:nbn:de:0030-drops-197252}, doi = {10.4230/LIPIcs.STACS.2024.15}, annote = {Keywords: Minimum Linear Arrangement, dynamic Variant, Optimization Problems, Graph Problems, approximation Algorithms} }
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} }