LIPIcs, Volume 275
APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA
Editors: Nicole Megow and Adam Smith
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Mikkel Abrahamsen, Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, and László Kozma. Online Sorting and Online TSP: Randomized, Stochastic, and High-Dimensional. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abrahamsen_et_al:LIPIcs.ESA.2024.5, author = {Abrahamsen, Mikkel and Bercea, Ioana O. and Beretta, Lorenzo and Klausen, Jonas and Kozma, L\'{a}szl\'{o}}, title = {{Online Sorting and Online TSP: Randomized, Stochastic, and High-Dimensional}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {5:1--5: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.5}, URN = {urn:nbn:de:0030-drops-210766}, doi = {10.4230/LIPIcs.ESA.2024.5}, annote = {Keywords: sorting, online algorithm, TSP} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Konstantinos Dogeas, Thomas Erlebach, and Ya-Chun Liang. Scheduling with Obligatory Tests. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dogeas_et_al:LIPIcs.ESA.2024.48, author = {Dogeas, Konstantinos and Erlebach, Thomas and Liang, Ya-Chun}, title = {{Scheduling with Obligatory Tests}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {48:1--48:14}, 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.48}, URN = {urn:nbn:de:0030-drops-211194}, doi = {10.4230/LIPIcs.ESA.2024.48}, annote = {Keywords: Competitive ratio, Online algorithm, Scheduling with testing, Sum of completion times} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Bingbing Hu, Evangelos Kosinas, and Adam Polak. Connectivity Oracles for Predictable Vertex Failures. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 72:1-72:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hu_et_al:LIPIcs.ESA.2024.72, author = {Hu, Bingbing and Kosinas, Evangelos and Polak, Adam}, title = {{Connectivity Oracles for Predictable Vertex Failures}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {72:1--72:16}, 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.72}, URN = {urn:nbn:de:0030-drops-211437}, doi = {10.4230/LIPIcs.ESA.2024.72}, annote = {Keywords: Data structures, graph connectivity, algorithms with predictions} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Shuchi Chawla and Dimitris Christou. Online Time-Windows TSP with Predictions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chawla_et_al:LIPIcs.APPROX/RANDOM.2024.2, author = {Chawla, Shuchi and Christou, Dimitris}, title = {{Online Time-Windows TSP with Predictions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {2:1--2: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.2}, URN = {urn:nbn:de:0030-drops-209954}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.2}, annote = {Keywords: Travelling Salesman Problem, Predictions, Learning-Augmented Algorithms, Approximation} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Josef Minařík and Jiří Sgall. Speed-Robust Scheduling Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{minarik_et_al:LIPIcs.APPROX/RANDOM.2024.8, author = {Mina\v{r}{\'\i}k, Josef and Sgall, Ji\v{r}{\'\i}}, title = {{Speed-Robust Scheduling Revisited}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {8:1--8:20}, 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.8}, URN = {urn:nbn:de:0030-drops-210010}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.8}, annote = {Keywords: scheduling, approximation algorithms, makespan, uniform speeds} }
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)
Moritz Buchem, Franziska Eberle, Hugo Kooki Kasuya Rosado, Kevin Schewior, and Andreas Wiese. Scheduling on a Stochastic Number of Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{buchem_et_al:LIPIcs.APPROX/RANDOM.2024.14, author = {Buchem, Moritz and Eberle, Franziska and Kasuya Rosado, Hugo Kooki and Schewior, Kevin and Wiese, Andreas}, title = {{Scheduling on a Stochastic Number of Machines}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {14:1--14:15}, 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.14}, URN = {urn:nbn:de:0030-drops-210073}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.14}, annote = {Keywords: scheduling, approximation algorithms, stochastic machines, makespan, max-min fair allocation, dynamic programming} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Evripidis Bampis, Konstantinos Dogeas, Thomas Erlebach, Nicole Megow, Jens Schlöter, and Amitabh Trehan. Competitive Query Minimization for Stable Matching with One-Sided Uncertainty. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bampis_et_al:LIPIcs.APPROX/RANDOM.2024.17, author = {Bampis, Evripidis and Dogeas, Konstantinos and Erlebach, Thomas and Megow, Nicole and Schl\"{o}ter, Jens and Trehan, Amitabh}, title = {{Competitive Query Minimization for Stable Matching with One-Sided Uncertainty}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {17:1--17: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.17}, URN = {urn:nbn:de:0030-drops-210100}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.17}, annote = {Keywords: Matching under Preferences, Stable Marriage, Query-Competitive Algorithms, Uncertainty} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Jakub Tětek. Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{tetek:LIPIcs.APPROX/RANDOM.2024.73, author = {T\v{e}tek, Jakub}, title = {{Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {73:1--73:20}, 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.73}, URN = {urn:nbn:de:0030-drops-210660}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.73}, annote = {Keywords: Differential privacy, Randomized approximation algorithms} }
Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)
Mario Günzel, Georg von der Brüggen, and Jian-Jia Chen. Tighter Worst-Case Response Time Bounds for Jitter-Based Self-Suspension Analysis. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gunzel_et_al:LIPIcs.ECRTS.2024.4, author = {G\"{u}nzel, Mario and von der Br\"{u}ggen, Georg and Chen, Jian-Jia}, title = {{Tighter Worst-Case Response Time Bounds for Jitter-Based Self-Suspension Analysis}}, booktitle = {36th Euromicro Conference on Real-Time Systems (ECRTS 2024)}, pages = {4:1--4:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-324-9}, ISSN = {1868-8969}, year = {2024}, volume = {298}, editor = {Pellizzoni, Rodolfo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.4}, URN = {urn:nbn:de:0030-drops-203074}, doi = {10.4230/LIPIcs.ECRTS.2024.4}, annote = {Keywords: Worst-Case Response Time, WCRT, Jitter, Self-Suspension, Analysis} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yusuke Kobayashi and Tatsuya Terao. Subquadratic Submodular Maximization with a General Matroid Constraint. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 100:1-100:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kobayashi_et_al:LIPIcs.ICALP.2024.100, author = {Kobayashi, Yusuke and Terao, Tatsuya}, title = {{Subquadratic Submodular Maximization with a General Matroid Constraint}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {100:1--100:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.100}, URN = {urn:nbn:de:0030-drops-202437}, doi = {10.4230/LIPIcs.ICALP.2024.100}, annote = {Keywords: submodular maximization, matroid constraint, approximation algorithm, rounding algorithm, query complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand, and Sebastian Siebertz. Solution Discovery via Reconfiguration for Problems in P. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 76:1-76:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{grobler_et_al:LIPIcs.ICALP.2024.76, author = {Grobler, Mario and Maaz, Stephanie and Megow, Nicole and Mouawad, Amer E. and Ramamoorthi, Vijayaragunathan and Schmand, Daniel and Siebertz, Sebastian}, title = {{Solution Discovery via Reconfiguration for Problems in P}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {76:1--76:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.76}, URN = {urn:nbn:de:0030-drops-202195}, doi = {10.4230/LIPIcs.ICALP.2024.76}, annote = {Keywords: solution discovery, reconfiguration, spanning tree, shortest path, matching, cut} }
Published in: Dagstuhl Reports, Volume 13, Issue 2 (2023)
Nicole Megow, Benjamin J. Moseley, David Shmoys, Ola Svensson, Sergei Vassilvitskii, and Jens Schlöter. Scheduling (Dagstuhl Seminar 23061). In Dagstuhl Reports, Volume 13, Issue 2, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{megow_et_al:DagRep.13.2.1, author = {Megow, Nicole and Moseley, Benjamin J. and Shmoys, David and Svensson, Ola and Vassilvitskii, Sergei and Schl\"{o}ter, Jens}, title = {{Scheduling (Dagstuhl Seminar 23061)}}, pages = {1--19}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {13}, number = {2}, editor = {Megow, Nicole and Moseley, Benjamin J. and Shmoys, David and Svensson, Ola and Vassilvitskii, Sergei and Schl\"{o}ter, Jens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.2.1}, URN = {urn:nbn:de:0030-drops-191789}, doi = {10.4230/DagRep.13.2.1}, annote = {Keywords: scheduling, mathematical optimization, approximation algorithms, learning methods, uncertainty} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 1-1304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Proceedings{megow_et_al:LIPIcs.APPROX/RANDOM.2023, title = {{LIPIcs, Volume 275, APPROX/RANDOM 2023, Complete Volume}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {1--1304}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023}, URN = {urn:nbn:de:0030-drops-188246}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023}, annote = {Keywords: LIPIcs, Volume 275, APPROX/RANDOM 2023, Complete Volume} }
Feedback for Dagstuhl Publishing