Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
Christopher Hahn, Jonas Harbig, and Peter Kling. Forming Large Patterns with Local Robots in the OBLOT Model. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hahn_et_al:LIPIcs.SAND.2024.14, author = {Hahn, Christopher and Harbig, Jonas and Kling, Peter}, title = {{Forming Large Patterns with Local Robots in the OBLOT Model}}, booktitle = {3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, pages = {14:1--14:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-315-7}, ISSN = {1868-8969}, year = {2024}, volume = {292}, editor = {Casteigts, Arnaud and Kuhn, Fabian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.14}, URN = {urn:nbn:de:0030-drops-198924}, doi = {10.4230/LIPIcs.SAND.2024.14}, annote = {Keywords: Swarm Algorithm, Swarm Robots, Distributed Algorithm, Pattern Formation, Limited Visibility, Oblivious} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Christoph Damerius, Peter Kling, Minming Li, Chenyang Xu, and Ruilong Zhang. Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{damerius_et_al:LIPIcs.ESA.2023.38, author = {Damerius, Christoph and Kling, Peter and Li, Minming and Xu, Chenyang and Zhang, Ruilong}, title = {{Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {38:1--38: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.38}, URN = {urn:nbn:de:0030-drops-186915}, doi = {10.4230/LIPIcs.ESA.2023.38}, annote = {Keywords: scheduling, total completion time, makespan, LP rounding, competitive analysis, approximation algorithm, NP hardness, PTAS} }
Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)
Jannik Castenow, Jonas Harbig, Daniel Jung, Peter Kling, Till Knollmann, and Friedhelm Meyer auf der Heide. A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 15:1-15:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{castenow_et_al:LIPIcs.OPODIS.2022.15, author = {Castenow, Jannik and Harbig, Jonas and Jung, Daniel and Kling, Peter and Knollmann, Till and Meyer auf der Heide, Friedhelm}, title = {{A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility}}, booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)}, pages = {15:1--15:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-265-5}, ISSN = {1868-8969}, year = {2023}, volume = {253}, editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.15}, URN = {urn:nbn:de:0030-drops-176350}, doi = {10.4230/LIPIcs.OPODIS.2022.15}, annote = {Keywords: mobile robots, gathering, limited visibility, runtime, collision avoidance, near-gathering} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Franziska Eberle, Nicole Megow, Lukas Nölke, Bertrand Simon, and Andreas Wiese. Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{eberle_et_al:LIPIcs.FSTTCS.2021.18, author = {Eberle, Franziska and Megow, Nicole and N\"{o}lke, Lukas and Simon, Bertrand and Wiese, Andreas}, title = {{Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {18:1--18:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.18}, URN = {urn:nbn:de:0030-drops-155297}, doi = {10.4230/LIPIcs.FSTTCS.2021.18}, annote = {Keywords: Fully dynamic algorithms, knapsack problem, approximation schemes} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Christoph Damerius, Dominik Kaaser, Peter Kling, and Florian Schneider. On Greedily Packing Anchored Rectangles. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{damerius_et_al:LIPIcs.ICALP.2021.61, author = {Damerius, Christoph and Kaaser, Dominik and Kling, Peter and Schneider, Florian}, title = {{On Greedily Packing Anchored Rectangles}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {61:1--61:20}, 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.61}, URN = {urn:nbn:de:0030-drops-141306}, doi = {10.4230/LIPIcs.ICALP.2021.61}, annote = {Keywords: lower-left anchored rectangle packing, greedy algorithm, charging scheme} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, and Lukas Nölke. On the Complexity of Anchored Rectangle Packing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{antoniadis_et_al:LIPIcs.ESA.2019.8, author = {Antoniadis, Antonios and Biermeier, Felix and Cristi, Andr\'{e}s and Damerius, Christoph and Hoeksma, Ruben and Kaaser, Dominik and Kling, Peter and N\"{o}lke, Lukas}, title = {{On the Complexity of Anchored Rectangle Packing}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {8:1--8: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.8}, URN = {urn:nbn:de:0030-drops-111297}, doi = {10.4230/LIPIcs.ESA.2019.8}, annote = {Keywords: anchored rectangle, rectangle packing, resource augmentation, PTAS, NP, hardness} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{berenbrink_et_al:LIPIcs.DISC.2018.10, author = {Berenbrink, Petra and Els\"{a}sser, Robert and Friedetzky, Tom and Kaaser, Dominik and Kling, Peter and Radzik, Tomasz}, title = {{A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.10}, URN = {urn:nbn:de:0030-drops-97999}, doi = {10.4230/LIPIcs.DISC.2018.10}, annote = {Keywords: Population Protocols, Randomized Algorithms, Majority} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{berenbrink_et_al:OASIcs.SOSA.2018.9, author = {Berenbrink, Petra and Kaaser, Dominik and Kling, Peter and Otterbach, Lena}, title = {{Simple and Efficient Leader Election}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {9:1--9:11}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9}, URN = {urn:nbn:de:0030-drops-83029}, doi = {10.4230/OASIcs.SOSA.2018.9}, annote = {Keywords: population protocols, leader election, distributed, randomized} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Petra Berenbrink, Tom Friedetzky, George Giakkoupis, and Peter Kling. Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 136:1-136:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{berenbrink_et_al:LIPIcs.ICALP.2016.136, author = {Berenbrink, Petra and Friedetzky, Tom and Giakkoupis, George and Kling, Peter}, title = {{Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {136:1--136:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.136}, URN = {urn:nbn:de:0030-drops-62711}, doi = {10.4230/LIPIcs.ICALP.2016.136}, annote = {Keywords: plurality consensus, voting, majority, distributed, gossip} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, and Chris Wastell. Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{berenbrink_et_al:LIPIcs.ESA.2016.10, author = {Berenbrink, Petra and Friedetzky, Tom and Kling, Peter and Mallmann-Trenn, Frederik and Wastell, Chris}, title = {{Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.10}, URN = {urn:nbn:de:0030-drops-63610}, doi = {10.4230/LIPIcs.ESA.2016.10}, annote = {Keywords: Plurality Consensus, Distributed Computing, Load Balancing} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Antonios Antoniadis, Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato. Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 63-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{antoniadis_et_al:LIPIcs.STACS.2014.63, author = {Antoniadis, Antonios and Barcelo, Neal and Consuegra, Mario and Kling, Peter and Nugent, Michael and Pruhs, Kirk and Scquizzato, Michele}, title = {{Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {63--74}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.63}, URN = {urn:nbn:de:0030-drops-44474}, doi = {10.4230/LIPIcs.STACS.2014.63}, annote = {Keywords: scheduling, flow time, energy efficiency, speed scaling, primal-dual} }
Feedback for Dagstuhl Publishing