Konfliktlösung und Optimierung
Theoretische Informatik
Zusammenfassung der Projektergebnisse
The goal of Project B1, “Conflict Resolution and Optimization”, was the development of general methods and tools for changing applications on flexible platforms that can be used in different and changing circumstances. Our objectives were to combine aspects of theory (developing general methods) and practice (aiming at practical methods that are useful in specific application scenarios). A particular focus was on scenarios with the necessity to adapt to incremental changes, which required developing sound theoretical methods, in the general context of the Research Unit as well as in specific application scenarios. Another challenge was to develop the mathematical background and tools for the practical projects of the Research Unit. First, we studied a number of new results for the aspects of Reallocation and Reconfiguration. For scheduling tasks in the context of change, we developed methods for achieving and maintaining feasibility of a solution, possibly at the expense of performing some change to a preliminary schedule. For a variety of applications in space, we worked in close cooperation with research unit C1 for developing energy-efficient computation and computation with limited resources, with a special focus on reconfigurable computing on FPGAs for practical applications in space missions. Second, we provided a number of important optimization methods for Concurrency, Conflicts and Allocation. We were able to provide fundamental progress in the context of concurrent robot navigation, where the objective is to coordinate the collision-free reconfiguration of a (potentially large) swarm of mobile components in an efficient manner, making use of parallelism. We also achieved algorithmic breakthroughs for a variety of problems in conflict-free coloring, including for multi-criteria optimization. For aspects of resource allocation corresponding to geometric packing, we were able to establish tight, new worst-case bounds on achievable packing density. Third, we developed new ideas and gave results for Distributed and Robust Methods, and Game Theory. We introduced and established the power of a new concept for parallel and robust optimization with incomplete information, inspired by concepts of redundancy. For this notion of k-copy online algorithms, we provided scenarios and methods that can beat the established lower bounds for single decision processes, making constructive use of the power of redundancy. Combining competitive and cooperative elements of resource allocation scenarios, we also studied efficient resource allocation from a game-theoretic point of view, and gave results on equilibria and algorithmic strategies.
Projektbezogene Publikationen (Auswahl)
- A Competitive Strategy for Distance-Aware Online Shape Allocation. Theoretical Computer Science, 555 (2014), pp. 43-54
S.P. Fekete, J.-M. Reinhardt, N. Schweer
(Siehe online unter https://doi.org/10.1016/j.tcs.2014.02.050) - Efficient Reconfiguration of Processing Modules on FPGAs for Space Instruments. Proc. 8th NASA/ESA Conf. Adaptive Hardware and Systems (AHS 2014), pp. 15-22
S.P. Fekete, S. Friedrichs, B. Fiethe, H. Michalik, C. Orlis
(Siehe online unter https://doi.org/10.1109/AHS.2014.6880153) - Cost-Oblivious Reallocation for Scheduling and Planning. In: 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2015), pp. 143-154
M.E. Bender, M. Farach-Colton, S.P. Fekete, J. Fineman, S. Gilbert
(Siehe online unter https://doi.org/10.1145/2755573.2755589) - Reallocation Problems in Scheduling. Algorithmica, October 2015, Volume 73, Issue 2, pp. 389-409
M.E. Bender, M. Farach-Colton, S.P. Fekete, J. Fineman, S. Gilbert
(Siehe online unter https://doi.org/10.1007/s00453-014-9930-4) - An Efficient Data Structure for Dynamic Two-Dimensional Reconfiguration. Journal of Systems Architecture, 75, April 2017, pp. 15-25
S.P. Fekete, J.-M. Reinhardt, C. Scheffer
(Siehe online unter https://doi.org/10.1016/j.sysarc.2017.02.004) - Cost-Oblivious Storage Reallocation. ACM Transactions on Algorithms, 13(3) 2017, article 38
M.E. Bender, M. Farach-Colton, S.P. Fekete, J. Fineman, S. Gilbert
(Siehe online unter https://doi.org/10.1145/3070693) - Resource-Efficient Dynamic Partial Reconfiguration on FPGAs for Space Instruments. Proc. 11th NASA/ESA Conf. Adaptive Hardware and Systems (AHS 2017), pp. 24-31
A. Dörflinger, B. Fiethe, H. Michalik, S.P. Fekete, P. Keldenich, C. Scheffer
(Siehe online unter https://doi.org/10.1109/AHS.2017.8046355) - Conflict-Free Coloring of Graphs. SIAM J. Discrete Mathematics, 32(4), 2018, pp. 2675-2702
Z. Abel, V. Alvarez, E.D. Demaine, S. Fekete, A. Gour, A. Hesterberg, P. Keldenich, C. Scheffer
(Siehe online unter https://doi.org/10.1137/17M1146579) - Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. Proc. 34th Int. Symp. Computational Geometry (SoCG 2018), pp. 29:1-29:15
E.D. Demaine, S.P. Fekete, P. Keldenich, H. Meijer, C. Scheffer
(Siehe online unter https://doi.org/10.4230/LIPIcs.SoCG.2018.29) - Hardware and Software Task Scheduling for ARM-FPGA Platforms. Proc. 12th NASA/ESA Conf. Adaptive Hardware and Systems (AHS 2018), pp. 66-73
A. Dörflinger, M. Albers, B. Fiethe, J. Schlatow, H. Michalik, P. Keldenich, S.P. Fekete
(Siehe online unter https://doi.org/10.1109/AHS.2018.8541481) - Packing Disks into Disks with Optimal Worst-Case Density: Proc. 35th Int. Symp. Computational Geometry (SoCG 2019), pp. 35:1-35:19
S.P. Fekete, P. Keldenich, C. Scheffer
(Siehe online unter https://doi.org/10.4230/LIPIcs.SoCG.2019.35) - Parallel Online Algorithms for the Bin Packing Problem. Proc. 17th Workshop on Approximation and Online Algorithms (WAOA 2019)
S.P. Fekete, J. Grosse-Holz, P. Keldenich, A. Schmidt
(Siehe online unter https://doi.org/10.1007/978-3-030-39479-0_8)
