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 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Aaron Berger, Jenny Kaufmann, and Virginia Vassilevska Williams. Approximating Min-Diameter: Standard and Bichromatic. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 17:1-17:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{berger_et_al:LIPIcs.ESA.2023.17, author = {Berger, Aaron and Kaufmann, Jenny and Vassilevska Williams, Virginia}, title = {{Approximating Min-Diameter: Standard and Bichromatic}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {17:1--17:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.17}, URN = {urn:nbn:de:0030-drops-186705}, doi = {10.4230/LIPIcs.ESA.2023.17}, annote = {Keywords: diameter, min distances, fine-grained, approximation algorithm} }
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Ruben Becker, Pierluigi Crescenzi, Antonio Cruciani, and Bojana Kodric. Proxying Betweenness Centrality Rankings in Temporal Networks. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 6:1-6:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{becker_et_al:LIPIcs.SEA.2023.6, author = {Becker, Ruben and Crescenzi, Pierluigi and Cruciani, Antonio and Kodric, Bojana}, title = {{Proxying Betweenness Centrality Rankings in Temporal Networks}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {6:1--6:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.6}, URN = {urn:nbn:de:0030-drops-183568}, doi = {10.4230/LIPIcs.SEA.2023.6}, annote = {Keywords: node centrality, betweenness, temporal graphs, graph mining} }
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt. Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 10:1-10:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{angrick_et_al:LIPIcs.SEA.2023.10, author = {Angrick, Sebastian and Bals, Ben and Casel, Katrin and Cohen, Sarel and Friedrich, Tobias and Hastrich, Niko and Hradilak, Theresa and Issac, Davis and Ki{\ss}ig, Otto and Schmidt, Jonas and Wendt, Leo}, title = {{Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {10:1--10:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.10}, URN = {urn:nbn:de:0030-drops-183602}, doi = {10.4230/LIPIcs.SEA.2023.10}, annote = {Keywords: directed feedback vertex set, vertex cover, reduction rules} }
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} }
Feedback for Dagstuhl Publishing