MMM
How Robots Learn to Use Structure
MMM Seed Grant Project
Project Highlights
Welcome to the webpage of the MMM project "How Robots Learn to Use Structure." This initiative focuses on addressing foundational algorithmic challenges to enable the integration of autonomous systems into societal infrastructure. By combining multivariate algorithmics, machine learning, and optimization under uncertainty, this project aims to develop efficient, fair, and decentralized solutions with rigorous guarantees on quality.
Research Publications
Michael R. Fellows
, Mario Grobler, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi,
Frances A. Rosamond, Daniel Schmand, Sebastian Siebertz:
On Solution Discovery via Reconfiguration. ECAI 2023: 700-707
https://ebooks.iospress.nl/doi/10.3233/FAIA230334
This paper explores the concept of solution discovery through reconfiguration, a process that involves transforming one solution of a problem into another in a step-by-step manner. The work delves into the theoretical underpinnings of reconfiguration in computational problems and demonstrates its applicability in various graph-based contexts. Key contributions include identifying critical structural parameters and presenting novel algorithms to navigate the reconfiguration space efficiently.
Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi,
Daniel Schmand, Sebastian Siebertz:
Solution Discovery via Reconfiguration for Problems in P. ICALP 2024: 76:1-76:20
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.76
Extending the concept of reconfiguration, this publication focuses on problems in the complexity class P. It presents a comprehensive framework to analyze how reconfiguration can be used to transition between solutions for problems that are solvable in polynomial time. The paper provides evidence that even for problems in P, reconfiguration offers unique computational challenges and opportunities, along with efficient strategies for practical implementations.
Mario Grobler, Stephanie Maaz, Amer E. Mouawad, Naomi Nishimura, Vijayaragunathan Ramamoorthi, Sebastian Siebertz:
Kernelization Complexity of Solution Discovery Problems. ISAAC 2024: 36:1-36:17
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.36
This article examines the kernelization complexity of solution discovery problems. Kernelization, a preprocessing technique in parameterized complexity, reduces the problem size while preserving its solvability. The authors uncover both positive and negative results regarding kernelization for a range of problems, shedding light on when efficient preprocessing is possible and when it is inherently limited. These findings offer valuable insights for designing algorithms that leverage structural properties of problem instances.
Workshops
MMM Workshop on Combinatorial Reconfiguration and Beyond
Date: November 28-29, 2024
Organizers: Nicole Megow, Daniel Schmand, Sebastian Siebertz
Description: This workshop brought together experts in combinatorial optimization, reconfiguration, and related fields to discuss advances in theory and applications. Topics included network reconfiguration, routing under uncertainty, and algorithmic game theory.
https://www.uni-bremen.de/en/theorie/bremen-workshop-on-combinatorial-reconfiguration-and-beyond
Bremen-Hamburg Colloquium on Algorithms, Combinatorics and Optimization
Date: November 30, 2024
Organizers: Nicole Megow, Daniel Schmand, Sebastian Siebertz
Description: This colloquium provided a platform for researchers from Bremen and Hamburg to collaborate on algorithms, combinatorics, and optimization. It featured talks, discussions, and networking opportunities to foster interdisciplinary research.
Conclusion
This project has made significant strides in advancing our understanding of how robots can learn and utilize structural properties of networks and systems. Through publications, workshops, and collaborations, we aim to shape the future of autonomous systems to be efficient, safe, and aligned with societal needs.