Publications

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, Tomasz Radzik (2021). Time-space trade-offs in population protocols for the majority problem. Distributed Comput..

PDF DOI

Antonios Antoniadis, Margarita Capretto, Parinya Chalermsook, Christoph Damerius, Peter Kling, Lukas Nölke, Nidia Obscura Acosta, Joachim Spoerhase (2021). On Minimum Generalized Manhattan Connections. Algorithms and Data Structures - 17th International Symposium, WADS 2021, Virtual Event, August 9-11, 2021, Proceedings.

PDF DOI

Christoph Damerius, Dominik Kaaser, Peter Kling, Florian Schneider (2021). On Greedily Packing Anchored Rectangles. CoRR.

PDF

Christoph Damerius, Dominik Kaaser, Peter Kling, Florian Schneider (2021). On Greedily Packing Anchored Rectangles. 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference).

PDF DOI

Petra Berenbrink, Tom Friedetzky, Christopher Hahn, Lukas Hintze, Dominik Kaaser, Peter Kling, Lars Nagel (2021). Infinite Balanced Allocation via Finite Capacities. 41st IEEE International Conference on Distributed Computing Systems, ICDCS 2021, Washington DC, USA, July 7-10, 2021.

PDF DOI

Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, Peter Kling (2021). Fast Consensus via the Unconstrained Undecided State Dynamics. CoRR.

PDF

Petra Berenbrink, George Giakkoupis, Peter Kling (2020). Optimal time and space leader election in population protocols. Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020.

PDF DOI

Antonios Antoniadis, Margarita Capretto, Parinya Chalermsook, Christoph Damerius, Peter Kling, Lukas Nölke, Nidia Obscura, Joachim Spoerhase (2020). On Minimum Generalized Manhattan Connections. CoRR.

PDF

Christoph Damerius, Peter Kling, Minming Li, Florian Schneider, Ruilong Zhang (2020). Improved Scheduling with a Shared Resource via Structural Insights. Combinatorial Optimization and Applications - 14th International Conference, COCOA 2020, Dallas, TX, USA, December 11-13, 2020, Proceedings.

PDF DOI

Petra Berenbrink, George Giakkoupis, Peter Kling (2020). Brief Announcement: Optimal Time and Space Leader Election in Population Protocols. PODC ‘20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020.

PDF DOI

Jannik Castenow, Peter Kling, Till Knollmann, Friedhelm Meyer auf der Heide (2020). A Discrete and Continuous Study of the Max-Chain-Formation Problem: Slow Down to Speed up. SPAA ‘20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020.

PDF DOI

Jannik Castenow, Peter Kling, Till Knollmann, Friedhelm Meyer auf der Heide (2020). A Discrete and Continuous Study of the Max-Chain-Formation Problem - Slow down to Speed Up. Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, TX, USA, November 18-21, 2020, Proceedings.

PDF DOI

Jannik Castenow, Peter Kling, Till Knollmann, Friedhelm Meyer auf der Heide (2020). A Discrete and Continuous Study of the Max-Chain-Formation Problem. CoRR.

PDF

Florian Wilkens, Steffen Haas, Dominik Kaaser, Peter Kling, Mathias Fischer (2019). Towards Efficient Reconstruction of Attacker Lateral Movement. Proceedings of the 14th International Conference on Availability, Reliability and Security, ARES 2019, Canterbury, UK, August 26-29, 2019.

PDF DOI

Petra Berenbrink, Tom Friedetzky, Dominik Kaaser, Peter Kling (2019). Tight & Simple Load Balancing. 2019 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019, Rio de Janeiro, Brazil, May 20-24, 2019.

PDF DOI

Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, Lukas Nölke (2019). On the Complexity of Anchored Rectangle Packing. 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany.

PDF DOI

Peter Kling, Friedhelm Meyer auf der Heide (2019). Continuous Protocols for Swarm Robotics. Distributed Computing by Mobile Entities, Current Research in Moving and Computing.

PDF DOI

Petra Berenbrink, George Giakkoupis, Peter Kling (2018). Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018.

PDF DOI

Petra Berenbrink, Tom Friedetzky, Dominik Kaaser, Peter Kling (2018). Simple Load Balancing. CoRR.

PDF

Petra Berenbrink, Dominik Kaaser, Peter Kling, Lena Otterbach (2018). Simple and Efficient Leader Election. 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA.

PDF DOI

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel, Chris Wastell (2018). Self-Stabilizing Balls and Bins in Batches - The Power of Leaky Bins. Algorithmica.

PDF DOI

Ernst Althaus, André Brinkmann, Peter Kling, Friedhelm Meyer auf der Heide, Lars Nagel, Sören Riechers, Jirí Sgall, Tim Süß (2018). Scheduling shared continuous resources on many-cores. J. Sched..

PDF DOI

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, Tomasz Radzik (2018). Majority & Stabilization in Population Protocols. CoRR.

PDF

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, Tomasz Radzik (2018). A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States. 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018.

PDF DOI

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, Tomasz Radzik (2018). A population protocol for exact majority with O(log(^mbox5/3)n) stabilization time and asymptotically optimal number of states. CoRR.

PDF

Petra Berenbrink, Peter Kling, Christopher Liaw, Abbas Mehrabian (2017). Tight Load Balancing via Randomized Local Search. CoRR.

PDF

Petra Berenbrink, Peter Kling, Christopher Liaw, Abbas Mehrabian (2017). Tight Load Balancing Via Randomized Local Search. 2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017, Orlando, FL, USA, May 29 - June 2, 2017.

PDF DOI

Peter Kling, Alexander Mäcker, Sören Riechers, Alexander Skopalik (2017). Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource. Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017, Washington DC, USA, July 24-26, 2017.

PDF DOI

Petra Berenbrink, Andrea E. F. Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, Emanuele Natale (2017). Ignore or Comply?: On Breaking Symmetry in Consensus. Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017.

PDF DOI

Petra Berenbrink, Andrea E. F. Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, Emanuele Natale (2017). Ignore or Comply? On Breaking Symmetry in Consensus. CoRR.

PDF

Antonios Antoniadis, Neal Barcelo, Mario E. Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, Michele Scquizzato (2017). Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules. Algorithmica.

PDF DOI

Antonios Antoniadis, Peter Kling, Sebastian Ott, Sören Riechers (2017). Continuous speed scaling with variability: A simple and direct approach. Theor. Comput. Sci..

PDF DOI

Sebastian Abshoff, Peter Kling, Christine Markarian, Friedhelm Meyer auf der Heide, Peter Pietrzyk (2016). Towards the price of leasing online. J. Comb. Optim..

PDF DOI

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel, Christopher Wastell (2016). Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins [Extended Abstract]. Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016.

PDF DOI

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel, Chris Wastell (2016). Self-stabilizing Balls & Bins in Batches. CoRR.

PDF

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Chris Wastell (2016). Plurality Consensus via Shuffling: Lessons Learned from Load Balancing. CoRR.

PDF

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Chris Wastell (2016). Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing. 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark.

PDF DOI

Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs (2016). Optimal Speed Scaling with a Solar Cell - (Extended Abstract). Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016, Proceedings.

PDF DOI

Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs (2016). Optimal Speed Scaling with a Solar Cell. CoRR.

PDF

Petra Berenbrink, Tom Friedetzky, George Giakkoupis, Peter Kling (2016). Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy.

PDF DOI

Peter Kling, Peter Pietrzyk (2015). Profitable Scheduling on Multiple Speed-Scalable Processors. ACM Trans. Parallel Comput..

PDF DOI

Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs, Michele Scquizzato (2015). On the Complexity of Speed Scaling. Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II.

PDF DOI

Bastian Degener, Barbara Kempkes, Peter Kling, Friedhelm Meyer auf der Heide (2015). Linear and Competitive Strategies for Continuous Robot Formation Problems. ACM Trans. Parallel Comput..

PDF DOI

André Brinkmann, Peter Kling, Friedhelm Meyer auf der Heide, Lars Nagel, Sören Riechers, Tim Süß (2014). Scheduling shared continuous resources on many-cores. 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ‘14, Prague, Czech Republic - June 23 - 25, 2014.

PDF DOI

Peter Kling (2014). Energy-efficient scheduling algorithms.

PDF

Antonios Antoniadis, Neal Barcelo, Mario E. Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, Michele Scquizzato (2014). Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules. 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France.

PDF DOI

Peter Kling, Peter Pietrzyk (2013). Profitable scheduling on multiple speed-scalable processors. 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ‘13, Montreal, QC, Canada - July 23 - 25, 2013.

PDF DOI

Markus Happe, Friedhelm Meyer auf der Heide, Peter Kling, Marco Platzner, Christian Plessl (2013). On-The-Fly Computing: A novel paradigm for individualized IT services. 16th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing, ISORC 2013, Paderborn, Germany, June 19-21, 2013.

PDF DOI

Peter Kling, Andreas Cord-Landwehr, Frederik Mallmann-Trenn (2012). Slow Down and Sleep for Profit in Online Deadline Scheduling. Design and Analysis of Algorithms - First Mediterranean Conference on Algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3-5, 2012. Proceedings.

PDF DOI

Peter Kling, Andreas Cord-Landwehr, Frederik Mallmann-Trenn (2012). Slow Down & Sleep for Profit in Online Deadline Scheduling. CoRR.

PDF

Peter Kling, Peter Pietrzyk (2012). Profitable Scheduling on Multiple Speed-Scalable Processors. CoRR.

PDF

Barbara Kempkes, Peter Kling, Friedhelm Meyer auf der Heide (2012). Optimal and competitive runtime bounds for continuous, local gathering of mobile robots. 24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ‘12, Pittsburgh, PA, USA, June 25-27, 2012.

PDF DOI

Andreas Cord-Landwehr, Martina Hüllmann, Peter Kling, Alexander Setzer (2012). Basic Network Creation Games with Communication Interests. CoRR.

PDF

Andreas Cord-Landwehr, Martina Hüllmann, Peter Kling, Alexander Setzer (2012). Basic Network Creation Games with Communication Interests. Algorithmic Game Theory - 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012. Proceedings.

PDF DOI

Peter Kling, Friedhelm Meyer auf der Heide, Peter Pietrzyk (2012). An Algorithm for Online Facility Leasing. Structural Information and Communication Complexity - 19th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30-July 2, 2012, Revised Selected Papers.

PDF DOI

Peter Kling, Friedhelm Meyer auf der Heide (2011). Convergence of local communication chain strategies via linear transformations: or how to trade locality for speed. SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4-6, 2011 (Co-located with FCRC 2011).

PDF DOI

Andreas Cord-Landwehr, Bastian Degener, Matthias Fischer, Martina Hüllmann, Barbara Kempkes, Alexander Klaas, Peter Kling, Sven Kurras, Marcus Märtens, Friedhelm Meyer auf der Heide, Christoph Raupach, Kamil Swierkot, Daniel Warner, Christoph Weddemann, Daniel Wonisch (2011). Collisionless Gathering of Robots with an Extent. SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 22-28, 2011. Proceedings.

PDF DOI

Joachim Gehweiler, Peter Kling, Friedhelm Meyer auf der Heide (2011). An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment. Parallel Processing and Applied Mathematics - 9th International Conference, PPAM 2011, Torun, Poland, September 11-14, 2011. Revised Selected Papers, Part II.

PDF DOI

Andreas Cord-Landwehr, Bastian Degener, Matthias Fischer, Martina Hüllmann, Barbara Kempkes, Alexander Klaas, Peter Kling, Sven Kurras, Marcus Märtens, Friedhelm Meyer auf der Heide, Christoph Raupach, Kamil Swierkot, Daniel Warner, Christoph Weddemann, Daniel Wonisch (2011). A New Approach for Analyzing Convergence Algorithms for Mobile Robots. Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II.

PDF DOI

Patrick Briest, Bastian Degener, Barbara Kempkes, Peter Kling, Peter Pietrzyk (2011). A Distributed Approximation Algorithm for the Metric Uncapacitated Facility Location Problem in the Congest Model. CoRR.

PDF

Bastian Degener, Barbara Kempkes, Peter Kling, Friedhelm Meyer auf der Heide (2010). A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots. Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings.

PDF DOI