LIPIcs, Volume 87
ESA 2017, September 4-6, 2017, Vienna, Austria
Editors: Kirk Pruhs and Christian Sohler
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Lukas Drexler, Jan Eube, Kelin Luo, Heiko Röglin, Melanie Schmidt, and Julian Wargalla. Connected k-Center and k-Diameter Clustering. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{drexler_et_al:LIPIcs.ICALP.2023.50, author = {Drexler, Lukas and Eube, Jan and Luo, Kelin and R\"{o}glin, Heiko and Schmidt, Melanie and Wargalla, Julian}, title = {{Connected k-Center and k-Diameter Clustering}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {50:1--50:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.50}, URN = {urn:nbn:de:0030-drops-181024}, doi = {10.4230/LIPIcs.ICALP.2023.50}, annote = {Keywords: Approximation algorithms, Clustering, Connectivity constraints} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Peter Mörters, Christian Sohler, and Stefan Walzer. A Sublinear Local Access Implementation for the Chinese Restaurant Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{morters_et_al:LIPIcs.APPROX/RANDOM.2022.28, author = {M\"{o}rters, Peter and Sohler, Christian and Walzer, Stefan}, title = {{A Sublinear Local Access Implementation for the Chinese Restaurant Process}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {28:1--28:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.28}, URN = {urn:nbn:de:0030-drops-171500}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.28}, annote = {Keywords: Chinese restaurant process, Dirichlet process, sublinear time algorithm, random recursive tree, random permutation, random partition, Ewens distribution, simulation, local access implementation, continuous time embedding} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Artur Czumaj, Hendrik Fichtenberger, Pan Peng, and Christian Sohler. Testable Properties in General Graphs and Random Order Streaming. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{czumaj_et_al:LIPIcs.APPROX/RANDOM.2020.16, author = {Czumaj, Artur and Fichtenberger, Hendrik and Peng, Pan and Sohler, Christian}, title = {{Testable Properties in General Graphs and Random Order Streaming}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {16:1--16:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.16}, URN = {urn:nbn:de:0030-drops-126190}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.16}, annote = {Keywords: Graph property testing, sublinear algorithms, graph streaming algorithms} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Proceedings{pruhs_et_al:LIPIcs.ESA.2017, title = {{LIPIcs, Volume 87, ESA'17, Complete Volume}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017}, URN = {urn:nbn:de:0030-drops-79096}, doi = {10.4230/LIPIcs.ESA.2017}, annote = {Keywords: Data Structures, Nonnumerical Algorithms and Problems, Optimization, Discrete Mathematics, Mathematical Software, AlgorithmsProblem Solving, Control Methods, and Search, Computational Geometry and Object Modeling} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{pruhs_et_al:LIPIcs.ESA.2017.0, author = {Pruhs, Kirk and Sohler, Christian}, title = {{Front Matter, Table of Contents, Preface, Programm Commitees, External Reviewers}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {0:i--0:xx}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.0}, URN = {urn:nbn:de:0030-drops-78147}, doi = {10.4230/LIPIcs.ESA.2017.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Programm Commitees, External Reviewers} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
David P. Woodruff. Sketching for Geometric Problems (Invited Talk). In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 1:1-1:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{woodruff:LIPIcs.ESA.2017.1, author = {Woodruff, David P.}, title = {{Sketching for Geometric Problems}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {1:1--1:5}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.1}, URN = {urn:nbn:de:0030-drops-78848}, doi = {10.4230/LIPIcs.ESA.2017.1}, annote = {Keywords: dimensionality reduction, low rank approximation, projection, regression, sketching} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Peyman Afshani and Ingo van Duijn. Permuting and Batched Geometric Lower Bounds in the I/O Model. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{afshani_et_al:LIPIcs.ESA.2017.2, author = {Afshani, Peyman and van Duijn, Ingo}, title = {{Permuting and Batched Geometric Lower Bounds in the I/O Model}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {2:1--2:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.2}, URN = {urn:nbn:de:0030-drops-78695}, doi = {10.4230/LIPIcs.ESA.2017.2}, annote = {Keywords: I/O Model, Batched Geometric Queries, Lower Bounds, Permuting} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Peyman Afshani and Zhewei Wei. Independent Range Sampling, Revisited. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{afshani_et_al:LIPIcs.ESA.2017.3, author = {Afshani, Peyman and Wei, Zhewei}, title = {{Independent Range Sampling, Revisited}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {3:1--3:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.3}, URN = {urn:nbn:de:0030-drops-78592}, doi = {10.4230/LIPIcs.ESA.2017.3}, annote = {Keywords: data structures, range searching, range sampling, random sampling} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Pankaj K. Agarwal, Natan Rubin, and Micha Sharir. Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{agarwal_et_al:LIPIcs.ESA.2017.4, author = {Agarwal, Pankaj K. and Rubin, Natan and Sharir, Micha}, title = {{Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {4:1--4:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.4}, URN = {urn:nbn:de:0030-drops-78182}, doi = {10.4230/LIPIcs.ESA.2017.4}, annote = {Keywords: Approximate nearest neighbor search, k-flats, Polyhedral distance functions, Linear programming queries} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Dror Aiger, Haim Kaplan, and Micha Sharir. Output Sensitive Algorithms for Approximate Incidences and Their Applications. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{aiger_et_al:LIPIcs.ESA.2017.5, author = {Aiger, Dror and Kaplan, Haim and Sharir, Micha}, title = {{Output Sensitive Algorithms for Approximate Incidences and Their Applications}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {5:1--5:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.5}, URN = {urn:nbn:de:0030-drops-78224}, doi = {10.4230/LIPIcs.ESA.2017.5}, annote = {Keywords: Approximate incidences, near-neighbor reporting, duality, grid-based approximation} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Hassene Aissi, Ali Ridha Mahjoub, and R. Ravi. Randomized Contractions for Multiobjective Minimum Cuts. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{aissi_et_al:LIPIcs.ESA.2017.6, author = {Aissi, Hassene and Mahjoub, Ali Ridha and Ravi, R.}, title = {{Randomized Contractions for Multiobjective Minimum Cuts}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {6:1--6:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.6}, URN = {urn:nbn:de:0030-drops-78686}, doi = {10.4230/LIPIcs.ESA.2017.6}, annote = {Keywords: minimum cut, multiobjective optimization, budget constraints, graph algorithms, randomized algorithms} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Susanne Albers and Sebastian Schraink. Tight Bounds for Online Coloring of Basic Graph Classes. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{albers_et_al:LIPIcs.ESA.2017.7, author = {Albers, Susanne and Schraink, Sebastian}, title = {{Tight Bounds for Online Coloring of Basic Graph Classes}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {7:1--7:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.7}, URN = {urn:nbn:de:0030-drops-78268}, doi = {10.4230/LIPIcs.ESA.2017.7}, annote = {Keywords: graph coloring, online algorithms, lower bounds, randomization} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa. Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{antunes_et_al:LIPIcs.ESA.2017.8, author = {Antunes, Daniel and Mathieu, Claire and Mustafa, Nabil H.}, title = {{Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {8:1--8:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.8}, URN = {urn:nbn:de:0030-drops-78293}, doi = {10.4230/LIPIcs.ESA.2017.8}, annote = {Keywords: Planar graphs, Local search, Hall's theorem, Combinatorial optimization, Expansion} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. In-Place Parallel Super Scalar Samplesort (IPSSSSo). In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{axtmann_et_al:LIPIcs.ESA.2017.9, author = {Axtmann, Michael and Witt, Sascha and Ferizovic, Daniel and Sanders, Peter}, title = {{In-Place Parallel Super Scalar Samplesort (IPSSSSo)}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {9:1--9:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.9}, URN = {urn:nbn:de:0030-drops-78542}, doi = {10.4230/LIPIcs.ESA.2017.9}, annote = {Keywords: shared memory, parallel sorting, in-place algorithm, comparison-based sorting, branch prediction} }
Feedback for Dagstuhl Publishing