LIPIcs, Volume 87
ESA 2017, September 4-6, 2017, Vienna, Austria
Editors: Kirk Pruhs and Christian Sohler
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Hung Q. Ngo. On an Information Theoretic Approach to Cardinality Estimation (Invited Talk). In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 1:1-1:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ngo:LIPIcs.ICDT.2022.1, author = {Ngo, Hung Q.}, title = {{On an Information Theoretic Approach to Cardinality Estimation}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {1:1--1:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-223-5}, ISSN = {1868-8969}, year = {2022}, volume = {220}, editor = {Olteanu, Dan and Vortmeier, Nils}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.1}, URN = {urn:nbn:de:0030-drops-158750}, doi = {10.4230/LIPIcs.ICDT.2022.1}, annote = {Keywords: Cardinality Estimation, Information Theory, Polymatroid Bound, Worst-case Optimal Join} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Marilena Leichter, Benjamin Moseley, and Kirk Pruhs. An Efficient Reduction of a Gammoid to a Partition Matroid. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 62:1-62:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{leichter_et_al:LIPIcs.ESA.2021.62, author = {Leichter, Marilena and Moseley, Benjamin and Pruhs, Kirk}, title = {{An Efficient Reduction of a Gammoid to a Partition Matroid}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {62:1--62:13}, 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.62}, URN = {urn:nbn:de:0030-drops-146432}, doi = {10.4230/LIPIcs.ESA.2021.62}, annote = {Keywords: Matroid, Gammoid, Reduction, Algorithms} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Mahmoud Abo-Khamis, Ryan Curtin, Sungjin Im, Benjamin Moseley, Hung Ngo, Kirk Pruhs, and Alireza Samadian. An Approximation Algorithm for the Matrix Tree Multiplication Problem. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 6:1-6:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{abokhamis_et_al:LIPIcs.MFCS.2021.6, author = {Abo-Khamis, Mahmoud and Curtin, Ryan and Im, Sungjin and Moseley, Benjamin and Ngo, Hung and Pruhs, Kirk and Samadian, Alireza}, title = {{An Approximation Algorithm for the Matrix Tree Multiplication Problem}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {6:1--6:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.6}, URN = {urn:nbn:de:0030-drops-144464}, doi = {10.4230/LIPIcs.MFCS.2021.6}, annote = {Keywords: Matrix Multiplication, Approximation Algorithm} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Benjamin Moseley, Kirk Pruhs, Alireza Samadian, and Yuyan Wang. Relational Algorithms for k-Means Clustering. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 97:1-97:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{moseley_et_al:LIPIcs.ICALP.2021.97, author = {Moseley, Benjamin and Pruhs, Kirk and Samadian, Alireza and Wang, Yuyan}, title = {{Relational Algorithms for k-Means Clustering}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {97:1--97:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.97}, URN = {urn:nbn:de:0030-drops-141668}, doi = {10.4230/LIPIcs.ICALP.2021.97}, annote = {Keywords: k-means, clustering, approximation, big-data, databases} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Enoch Peserico and Michele Scquizzato. Matching on the Line Admits No o(√log n)-Competitive Algorithm. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 103:1-103:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{peserico_et_al:LIPIcs.ICALP.2021.103, author = {Peserico, Enoch and Scquizzato, Michele}, title = {{Matching on the Line Admits No o(√log n)-Competitive Algorithm}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {103:1--103:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.103}, URN = {urn:nbn:de:0030-drops-141720}, doi = {10.4230/LIPIcs.ICALP.2021.103}, annote = {Keywords: Metric matching, online algorithms, competitive analysis} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Sungjin Im, Benjamin Moseley, Kirk Pruhs, and Manish Purohit. Matroid Coflow Scheduling. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 145:1-145:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{im_et_al:LIPIcs.ICALP.2019.145, author = {Im, Sungjin and Moseley, Benjamin and Pruhs, Kirk and Purohit, Manish}, title = {{Matroid Coflow Scheduling}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {145:1--145:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.145}, URN = {urn:nbn:de:0030-drops-107213}, doi = {10.4230/LIPIcs.ICALP.2019.145}, annote = {Keywords: Coflow Scheduling, Concurrent Open Shop, Matroid Scheduling} }
Published in: LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1
Bader Naim Alahmad and Sathish Gopalakrishnan. Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions. In LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1, pp. 01:1-01:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@Article{alahmad_et_al:LITES-v005-i001-a001, author = {Alahmad, Bader Naim and Gopalakrishnan, Sathish}, title = {{Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions}}, booktitle = {LITES, Volume 5, Issue 1 (2018)}, pages = {01:1--01:30}, journal = {Leibniz Transactions on Embedded Systems}, ISSN = {2199-2002}, year = {2018}, volume = {5}, number = {1}, editor = {Alahmad, Bader Naim and Gopalakrishnan, Sathish}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LITES-v005-i001-a001}, doi = {10.4230/LITES-v005-i001-a001}, annote = {Keywords: Mixed criticalities, Probability distribution, Real time systems, Scheduling, Chance constrained Markov decision process, Linear programming, Randomized policy} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Kirk Pruhs and Christian Sohler. LIPIcs, Volume 87, ESA'17, Complete Volume. In 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.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)
Kirk Pruhs and Christian Sohler. Front Matter, Table of Contents, Preface, Programm Commitees, External Reviewers. In 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.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.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.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.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.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.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} }
Feedback for Dagstuhl Publishing