LIPIcs, Volume 173
ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference)
Editors: Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders
LIPIcs, Volume 49
FUN 2016, June 8-10, 2016, La Maddalena, Italy
Editors: Erik D. Demaine and Fabrizio Grandoni
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Miguel Bosch-Calvo, Fabrizio Grandoni, and Afrouz Jabal Ameli. A 4/3 Approximation for 2-Vertex-Connectivity. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 29:1-29:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{boschcalvo_et_al:LIPIcs.ICALP.2023.29, author = {Bosch-Calvo, Miguel and Grandoni, Fabrizio and Jabal Ameli, Afrouz}, title = {{A 4/3 Approximation for 2-Vertex-Connectivity}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {29:1--29:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.29}, URN = {urn:nbn:de:0030-drops-180813}, doi = {10.4230/LIPIcs.ICALP.2023.29}, annote = {Keywords: Algorithm, Network Design, Vertex-Connectivity, Approximation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Fabrizio Grandoni, Claire Mathieu, and Hang Zhou. Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 63:1-63:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{grandoni_et_al:LIPIcs.ITCS.2023.63, author = {Grandoni, Fabrizio and Mathieu, Claire and Zhou, Hang}, title = {{Unsplittable Euclidean Capacitated Vehicle Routing: A (2+\epsilon)-Approximation Algorithm}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {63:1--63:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.63}, URN = {urn:nbn:de:0030-drops-175660}, doi = {10.4230/LIPIcs.ITCS.2023.63}, annote = {Keywords: capacitated vehicle routing, approximation algorithms, Euclidean plane} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. Decremental Matching in General Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 11:1-11:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi_et_al:LIPIcs.ICALP.2022.11, author = {Assadi, Sepehr and Bernstein, Aaron and Dudeja, Aditi}, title = {{Decremental Matching in General Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.11}, URN = {urn:nbn:de:0030-drops-163528}, doi = {10.4230/LIPIcs.ICALP.2022.11}, annote = {Keywords: Dynamic algorithms, matching, primal-dual algorithms} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, and Kamyar Khodamoradi. Approximation Algorithms for Demand Strip Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 20:1-20:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{galvez_et_al:LIPIcs.APPROX/RANDOM.2021.20, author = {G\'{a}lvez, Waldo and Grandoni, Fabrizio and Ameli, Afrouz Jabal and Khodamoradi, Kamyar}, title = {{Approximation Algorithms for Demand Strip Packing}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {20:1--20:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.20}, URN = {urn:nbn:de:0030-drops-147130}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.20}, annote = {Keywords: Strip Packing, Two-Dimensional Packing, Approximation Algorithms} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese. Faster (1+ε)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 49:1-49:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{grandoni_et_al:LIPIcs.ESA.2021.49, author = {Grandoni, Fabrizio and M\"{o}mke, Tobias and Wiese, Andreas}, title = {{Faster (1+\epsilon)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {49:1--49: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.49}, URN = {urn:nbn:de:0030-drops-146301}, doi = {10.4230/LIPIcs.ESA.2021.49}, annote = {Keywords: Approximation Algorithms, Unsplittable Flow, Dynamic Programming} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, and Andreas Wiese. Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 39:1-39:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{galvez_et_al:LIPIcs.SoCG.2021.39, author = {G\'{a}lvez, Waldo and Grandoni, Fabrizio and Khan, Arindam and Ram{\'\i}rez-Romero, Diego and Wiese, Andreas}, title = {{Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {39:1--39:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.39}, URN = {urn:nbn:de:0030-drops-138386}, doi = {10.4230/LIPIcs.SoCG.2021.39}, annote = {Keywords: Approximation algorithms, two-dimensional knapsack, geometric packing} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders. LIPIcs, Volume 173, ESA 2020, Complete Volume. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 1-1598, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@Proceedings{grandoni_et_al:LIPIcs.ESA.2020, title = {{LIPIcs, Volume 173, ESA 2020, Complete Volume}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {1--1598}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020}, URN = {urn:nbn:de:0030-drops-128651}, doi = {10.4230/LIPIcs.ESA.2020}, annote = {Keywords: LIPIcs, Volume 173, ESA 2020, Complete Volume} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders. Front Matter, Table of Contents, Preface, Conference Organization. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 0:i-0:xx, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{grandoni_et_al:LIPIcs.ESA.2020.0, author = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {0:i--0:xx}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.0}, URN = {urn:nbn:de:0030-drops-128669}, doi = {10.4230/LIPIcs.ESA.2020.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, and Joseph S. B. Mitchell. Planar Bichromatic Bottleneck Spanning Trees. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 1:1-1:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{abuaffash_et_al:LIPIcs.ESA.2020.1, author = {Abu-Affash, A. Karim and Bhore, Sujoy and Carmi, Paz and Mitchell, Joseph S. B.}, title = {{Planar Bichromatic Bottleneck Spanning Trees}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {1:1--1:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.1}, URN = {urn:nbn:de:0030-drops-128670}, doi = {10.4230/LIPIcs.ESA.2020.1}, annote = {Keywords: Approximation Algorithms, Bottleneck Spanning Tree, NP-Hardness} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. Parallel Batch-Dynamic Trees via Change Propagation. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 2:1-2:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{acar_et_al:LIPIcs.ESA.2020.2, author = {Acar, Umut A. and Anderson, Daniel and Blelloch, Guy E. and Dhulipala, Laxman and Westrick, Sam}, title = {{Parallel Batch-Dynamic Trees via Change Propagation}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {2:1--2:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.2}, URN = {urn:nbn:de:0030-drops-128686}, doi = {10.4230/LIPIcs.ESA.2020.2}, annote = {Keywords: Dynamic trees, Graph algorithms, Parallel algorithms, Dynamic algorithms} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Reconstructing Biological and Digital Phylogenetic Trees in Parallel. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 3:1-3:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{afshar_et_al:LIPIcs.ESA.2020.3, author = {Afshar, Ramtin and Goodrich, Michael T. and Matias, Pedro and Osegueda, Martha C.}, title = {{Reconstructing Biological and Digital Phylogenetic Trees in Parallel}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {3:1--3:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.3}, URN = {urn:nbn:de:0030-drops-128696}, doi = {10.4230/LIPIcs.ESA.2020.3}, annote = {Keywords: Tree Reconstruction, Parallel Algorithms, Privacy, Phylogenetic Trees, Data Structures, Hierarchical Clustering} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, and Richard Spence. Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 4:1-4:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{ahmed_et_al:LIPIcs.ESA.2020.4, author = {Ahmed, Reyan and Sahneh, Faryad Darabi and Hamm, Keaton and Kobourov, Stephen and Spence, Richard}, title = {{Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {4:1--4:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.4}, URN = {urn:nbn:de:0030-drops-128709}, doi = {10.4230/LIPIcs.ESA.2020.4}, annote = {Keywords: multi-level, Steiner tree, approximation algorithms} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Amihood Amir, Itai Boneh, Michael Itzhaki, and Eitan Kondratovsky. Analysis of the Period Recovery Error Bound. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 5:1-5:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{amir_et_al:LIPIcs.ESA.2020.5, author = {Amir, Amihood and Boneh, Itai and Itzhaki, Michael and Kondratovsky, Eitan}, title = {{Analysis of the Period Recovery Error Bound}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {5:1--5:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.5}, URN = {urn:nbn:de:0030-drops-128717}, doi = {10.4230/LIPIcs.ESA.2020.5}, annote = {Keywords: Period Recovery, Period Recovery Hierarchy, Hamming Distance} }
Feedback for Dagstuhl Publishing