Conflict Resolution and Optimization

• Applicant: Professor Dr. Sándor Fekete
• Subject Area: Computer Architecture, Embedded and Massively Parallel Systems ; Theoretical Computer Science
• Term: from 2013 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 206480214

• Final Report Year: 2020

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
  
• 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
  
• 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
  
• 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
  
• 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
  
• 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
  
• 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
  
• 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
  
• 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
  
• 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
  
• 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
  
• 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