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)
Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz. Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{disser_et_al:LIPIcs.ESA.2024.47, author = {Disser, Yann and Griesbach, Svenja M. and Klimm, Max and Lutz, Annette}, title = {{Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {47:1--47: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.47}, URN = {urn:nbn:de:0030-drops-211188}, doi = {10.4230/LIPIcs.ESA.2024.47}, annote = {Keywords: incremental optimization, competitive analysis, prize-collecting Steiner-tree} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Toru Yoshinaga and Yasushi Kawase. The Last Success Problem with Samples. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 105:1-105:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{yoshinaga_et_al:LIPIcs.ESA.2024.105, author = {Yoshinaga, Toru and Kawase, Yasushi}, title = {{The Last Success Problem with Samples}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {105:1--105: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.105}, URN = {urn:nbn:de:0030-drops-211762}, doi = {10.4230/LIPIcs.ESA.2024.105}, annote = {Keywords: The Last Success Problem, Secretary Problem, Sample Information Model, Optimal Stopping, Online Algorithms} }
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)
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 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Niklas Schlomberg. An Improved Integrality Gap for Disjoint Cycles in Planar Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 122:1-122:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{schlomberg:LIPIcs.ICALP.2024.122, author = {Schlomberg, Niklas}, title = {{An Improved Integrality Gap for Disjoint Cycles in Planar Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {122:1--122:15}, 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.122}, URN = {urn:nbn:de:0030-drops-202651}, doi = {10.4230/LIPIcs.ICALP.2024.122}, annote = {Keywords: Cycle packing, planar graphs, disjoint paths} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Lisa Hellerstein, Naifeng Liu, and Kevin Schewior. Quickly Determining Who Won an Election. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hellerstein_et_al:LIPIcs.ITCS.2024.61, author = {Hellerstein, Lisa and Liu, Naifeng and Schewior, Kevin}, title = {{Quickly Determining Who Won an Election}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {61:1--61:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.61}, URN = {urn:nbn:de:0030-drops-195890}, doi = {10.4230/LIPIcs.ITCS.2024.61}, annote = {Keywords: stochastic function evaluation, voting, approximation algorithms} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Svenja M. Griesbach, Felix Hommelsheim, Max Klimm, and Kevin Schewior. Improved Approximation Algorithms for the Expanding Search Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{griesbach_et_al:LIPIcs.ESA.2023.54, author = {Griesbach, Svenja M. and Hommelsheim, Felix and Klimm, Max and Schewior, Kevin}, title = {{Improved Approximation Algorithms for the Expanding Search Problem}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {54:1--54:15}, 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.54}, URN = {urn:nbn:de:0030-drops-187073}, doi = {10.4230/LIPIcs.ESA.2023.54}, annote = {Keywords: Approximation Algorithm, Expanding Search, Search Problem, Graph Exploration, Traveling Repairperson Problem} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Martin Hoefer and Kevin Schewior. Threshold Testing and Semi-Online Prophet Inequalities. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hoefer_et_al:LIPIcs.ESA.2023.62, author = {Hoefer, Martin and Schewior, Kevin}, title = {{Threshold Testing and Semi-Online Prophet Inequalities}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {62:1--62:15}, 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.62}, URN = {urn:nbn:de:0030-drops-187159}, doi = {10.4230/LIPIcs.ESA.2023.62}, annote = {Keywords: Prophet Inequalities, Testing, Stochastic Probing} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Yann Disser, Max Klimm, Kevin Schewior, and David Weckbecker. Incremental Maximization via Continuization. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{disser_et_al:LIPIcs.ICALP.2023.47, author = {Disser, Yann and Klimm, Max and Schewior, Kevin and Weckbecker, David}, title = {{Incremental Maximization via Continuization}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {47:1--47:17}, 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.47}, URN = {urn:nbn:de:0030-drops-180992}, doi = {10.4230/LIPIcs.ICALP.2023.47}, annote = {Keywords: incremental optimization, competitive analysis, robust matching, submodular function} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
José Correa, Paul Dütting, Felix Fischer, Kevin Schewior, and Bruno Ziliotto. Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, p. 86:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{correa_et_al:LIPIcs.ITCS.2021.86, author = {Correa, Jos\'{e} and D\"{u}tting, Paul and Fischer, Felix and Schewior, Kevin and Ziliotto, Bruno}, title = {{Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {86:1--86:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.86}, URN = {urn:nbn:de:0030-drops-136255}, doi = {10.4230/LIPIcs.ITCS.2021.86}, annote = {Keywords: Prophet Inequalities, Stopping Theory, Unknown Distributions} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Franziska Eberle, Nicole Megow, and Kevin Schewior. Optimally Handling Commitment Issues in Online Throughput Maximization. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{eberle_et_al:LIPIcs.ESA.2020.41, author = {Eberle, Franziska and Megow, Nicole and Schewior, Kevin}, title = {{Optimally Handling Commitment Issues in Online Throughput Maximization}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {41:1--41:15}, 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.41}, URN = {urn:nbn:de:0030-drops-129076}, doi = {10.4230/LIPIcs.ESA.2020.41}, annote = {Keywords: Deadline scheduling, throughput, online algorithms, competitive analysis} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Alexander Birx, Yann Disser, and Kevin Schewior. Improved Bounds for Open Online Dial-a-Ride on the Line. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{birx_et_al:LIPIcs.APPROX-RANDOM.2019.21, author = {Birx, Alexander and Disser, Yann and Schewior, Kevin}, title = {{Improved Bounds for Open Online Dial-a-Ride on the Line}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {21:1--21:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.21}, URN = {urn:nbn:de:0030-drops-112367}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.21}, annote = {Keywords: dial-a-ride on the line, elevator problem, online algorithms, competitive analysis, smartstart, competitive ratio} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Evripidis Bampis, Bruno Escoffier, Kevin Schewior, and Alexandre Teiller. Online Multistage Subset Maximization Problems. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bampis_et_al:LIPIcs.ESA.2019.11, author = {Bampis, Evripidis and Escoffier, Bruno and Schewior, Kevin and Teiller, Alexandre}, title = {{Online Multistage Subset Maximization Problems}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.11}, URN = {urn:nbn:de:0030-drops-111320}, doi = {10.4230/LIPIcs.ESA.2019.11}, annote = {Keywords: Multistage optimization, Online algorithms} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Fábio Botler, Andrés Cristi, Ruben Hoeksma, Kevin Schewior, and Andreas Tönnis. SUPERSET: A (Super)Natural Variant of the Card Game SET. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{botler_et_al:LIPIcs.FUN.2018.12, author = {Botler, F\'{a}bio and Cristi, Andr\'{e}s and Hoeksma, Ruben and Schewior, Kevin and T\"{o}nnis, Andreas}, title = {{SUPERSET: A (Super)Natural Variant of the Card Game SET}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.12}, URN = {urn:nbn:de:0030-drops-88035}, doi = {10.4230/LIPIcs.FUN.2018.12}, annote = {Keywords: SET, SUPERSET, card game, cap set, affine geometry, computational complexity} }
Feedback for Dagstuhl Publishing