Conflict Resolution and Optimization
Theoretical Computer Science
Final Report Abstract
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.
Publications
- 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at https://doi.org/10.1007/978-3-030-39479-0_8)
