LIPIcs, Volume 33
CCC 2015, June 17-19, 2015, Portland, Oregon, USA
Editors: David Zuckerman
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Enver Aman, Karthik C. S., and Sharath Punna. On Connections Between k-Coloring and Euclidean k-Means. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aman_et_al:LIPIcs.ESA.2024.9, author = {Aman, Enver and Karthik C. S. and Punna, Sharath}, title = {{On Connections Between k-Coloring and Euclidean k-Means}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.9}, URN = {urn:nbn:de:0030-drops-210808}, doi = {10.4230/LIPIcs.ESA.2024.9}, annote = {Keywords: k-means, k-minsum, Euclidean space, fine-grained complexity} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Dipan Dey and Manoj Gupta. Near Optimal Dual Fault Tolerant Distance Oracle. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 45:1-45:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dey_et_al:LIPIcs.ESA.2024.45, author = {Dey, Dipan and Gupta, Manoj}, title = {{Near Optimal Dual Fault Tolerant Distance Oracle}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {45:1--45:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.45}, URN = {urn:nbn:de:0030-drops-211164}, doi = {10.4230/LIPIcs.ESA.2024.45}, annote = {Keywords: Distance Sensitive Oracle, Dual Fault Distance Oracle} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Shimon Kogan and Merav Parter. Giving Some Slack: Shortcuts and Transitive Closure Compressions. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 79:1-79:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kogan_et_al:LIPIcs.ESA.2024.79, author = {Kogan, Shimon and Parter, Merav}, title = {{Giving Some Slack: Shortcuts and Transitive Closure Compressions}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {79:1--79:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.79}, URN = {urn:nbn:de:0030-drops-211509}, doi = {10.4230/LIPIcs.ESA.2024.79}, annote = {Keywords: Reachability Shortcuts, Width, DAG} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Paloma T. Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, and Kenny Štorgel. Tree Decompositions Meet Induced Matchings: Beyond Max Weight Independent Set. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 85:1-85:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lima_et_al:LIPIcs.ESA.2024.85, author = {Lima, Paloma T. and Milani\v{c}, Martin and Mur\v{s}i\v{c}, Peter and Okrasa, Karolina and Rz\k{a}\.{z}ewski, Pawe{\l} and \v{S}torgel, Kenny}, title = {{Tree Decompositions Meet Induced Matchings: Beyond Max Weight Independent Set}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {85:1--85:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.85}, URN = {urn:nbn:de:0030-drops-211569}, doi = {10.4230/LIPIcs.ESA.2024.85}, annote = {Keywords: induced matching treewidth, tree-independence number, feedback vertex set, induced packing, algorithmic meta-theorem} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Slobodan Mitrović, Ronitt Rubinfeld, and Mihir Singhal. Locally Computing Edge Orientations. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 89:1-89:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mitrovic_et_al:LIPIcs.ESA.2024.89, author = {Mitrovi\'{c}, Slobodan and Rubinfeld, Ronitt and Singhal, Mihir}, title = {{Locally Computing Edge Orientations}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {89:1--89:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.89}, URN = {urn:nbn:de:0030-drops-211603}, doi = {10.4230/LIPIcs.ESA.2024.89}, annote = {Keywords: local computation algorithms, edge orientation, tree coloring} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Pu Wu, Huanyu Gu, Huiqin Jiang, Zehui Shao, and Jin Xu. A Faster Algorithm for the 4-Coloring Problem. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 103:1-103:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{wu_et_al:LIPIcs.ESA.2024.103, author = {Wu, Pu and Gu, Huanyu and Jiang, Huiqin and Shao, Zehui and Xu, Jin}, title = {{A Faster Algorithm for the 4-Coloring Problem}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {103:1--103:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.103}, URN = {urn:nbn:de:0030-drops-211749}, doi = {10.4230/LIPIcs.ESA.2024.103}, annote = {Keywords: Graph coloring, Graph algorithms, Exact algorithms} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Tomer Ezra, Stefano Leonardi, Michał Pawłowski, Matteo Russo, and Seeun William Umboh. Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ezra_et_al:LIPIcs.APPROX/RANDOM.2024.12, author = {Ezra, Tomer and Leonardi, Stefano and Paw{\l}owski, Micha{\l} and Russo, Matteo and Umboh, Seeun William}, title = {{Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {12:1--12:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.12}, URN = {urn:nbn:de:0030-drops-210050}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.12}, annote = {Keywords: Set Cover, Joint Replenishment, TCP-Acknowledgment, Subadditive Function Approximation, Multi-Level Aggregation} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, David Wajc, and Di Wang. The Average-Value Allocation Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bhawalkar_et_al:LIPIcs.APPROX/RANDOM.2024.13, author = {Bhawalkar, Kshipra and Feng, Zhe and Gupta, Anupam and Mehta, Aranyak and Wajc, David and Wang, Di}, title = {{The Average-Value Allocation Problem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {13:1--13:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.13}, URN = {urn:nbn:de:0030-drops-210062}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.13}, annote = {Keywords: Resource allocation, return-on-spend constraint, approximation algorithm, online algorithm} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang. Learning-Augmented Maximum Independent Set. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{braverman_et_al:LIPIcs.APPROX/RANDOM.2024.24, author = {Braverman, Vladimir and Dharangutte, Prathamesh and Shah, Vihan and Wang, Chen}, title = {{Learning-Augmented Maximum Independent Set}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {24:1--24:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.24}, URN = {urn:nbn:de:0030-drops-210179}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.24}, annote = {Keywords: Learning-augmented algorithms, maximum independent set, graph algorithms} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Amnon Ta-Shma and Ron Zadicario. The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{tashma_et_al:LIPIcs.APPROX/RANDOM.2024.31, author = {Ta-Shma, Amnon and Zadicario, Ron}, title = {{The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {31:1--31:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.31}, URN = {urn:nbn:de:0030-drops-210246}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.31}, annote = {Keywords: Expander random walks, Expander hitting property} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, and Chao Yan. Hilbert Functions and Low-Degree Randomness Extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 41:1-41:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{golovnev_et_al:LIPIcs.APPROX/RANDOM.2024.41, author = {Golovnev, Alexander and Guo, Zeyu and Hatami, Pooya and Nagargoje, Satyajeet and Yan, Chao}, title = {{Hilbert Functions and Low-Degree Randomness Extractors}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {41:1--41:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.41}, URN = {urn:nbn:de:0030-drops-210345}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.41}, annote = {Keywords: Extractors, Dispersers, Circuits, Hilbert Function, Randomness, Low Degree Polynomials} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Halley Goldberg and Valentine Kabanets. Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 51:1-51:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{goldberg_et_al:LIPIcs.APPROX/RANDOM.2024.51, author = {Goldberg, Halley and Kabanets, Valentine}, title = {{Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {51:1--51:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.51}, URN = {urn:nbn:de:0030-drops-210444}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.51}, annote = {Keywords: Meta-complexity, Randomized reductions, NP-hardness, Worst-case complexity, Time-bounded Kolmogorov complexity} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Reut Levi, Moti Medina, and Omer Tubul. Nearly Optimal Local Algorithms for Constructing Sparse Spanners of Clusterable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 60:1-60:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{levi_et_al:LIPIcs.APPROX/RANDOM.2024.60, author = {Levi, Reut and Medina, Moti and Tubul, Omer}, title = {{Nearly Optimal Local Algorithms for Constructing Sparse Spanners of Clusterable Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {60:1--60:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.60}, URN = {urn:nbn:de:0030-drops-210537}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.60}, annote = {Keywords: Locally Computable Algorithms, Sublinear algorithms, Spanning Subgraphs, Clusterbale Graphs} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Inbar Ben Yaacov, Yotam Dikstein, and Gal Maor. Sparse High Dimensional Expanders via Local Lifts. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 68:1-68:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{benyaacov_et_al:LIPIcs.APPROX/RANDOM.2024.68, author = {Ben Yaacov, Inbar and Dikstein, Yotam and Maor, Gal}, title = {{Sparse High Dimensional Expanders via Local Lifts}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {68:1--68:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.68}, URN = {urn:nbn:de:0030-drops-210612}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.68}, annote = {Keywords: High Dimensional Expanders, HDX, Spectral Expansion, Lifts, Covers, Explicit Constructions, Randomized Constructions, Deterministic Constructions} }
Feedback for Dagstuhl Publishing