Conflict Resolution and Optimization

冲突解决和优化

• 批准号: 230782768
• 负责人: Professor Dr. Sándor Fekete
• 金额: --
• 依托单位: Institut für Betriebssysteme und Rechnerverbund
• 依托单位国家: 德国
• 项目类别: Research Units
• 财政年份: 2013
• 资助国家: 德国
• 起止时间: 2012-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/230782768?language=en
• 关键词: Conflict; Resolution; Optimization

The main objectives of Phase 1 aim at developing fundamental algorithmic methods for reconfiguration and reallocation, as well as ensuring that they are useful and suitable for the overall objectives of CCC, by engaging in practical collaboration with the other, more applied projects. This is achieved by considering methods that work at different information and optimization scales (e.g., exact global computation by mathematical programming, heuristic approaches by local methods for gradual improvement), different time scales (e.g., more time-consuming methods applied in an offline setting, faster methods for online scenarios, but also a subdivision into preprocessing/query), as well as different computation scales (e.g., centralized computation vs. game-theoretic mechanism design). These scales are often linked (for example, decentralized computation may correlate with limited information), without being methodologically equivalent (e.g., optimization under limited information arises even in centralized scenarios, giving rise to the area of online algorithms). A general approach in the field of algorithmics is to develop separate methods for scenarios at different scales, i.e., to consider one combination of the described scales, and develop powerful methods that work well under these specific conditions.The main overall objective for Phase 2 is to overcome this limitation and study of multi-scale, integrated and interleaving methods for complex scenarios, in which these different scales (information and optimization, time, computation) are not treated separately, but are employed in an interchanging and parallel fashion. This requires blending and unifying the separate algorithmic methods into multi-scale methods, to be carried out within B1, a close interaction with the conceptual approaches and techniques of distributed contract and algorithm design and employment for complex, structured scenarios in collaboration with other projects, and an integration of the overall methods with the other projects in the context of case studies with the partners from the applied projects. Most notably, these involve studying robot platforms and autonomous vehicles, both of which pose relevant scientific challenges, when organizing resource allocation within one robot or vehicle and when coordinating several platforms. Beyond our algorithmic expertise, we have considerable experience in both application areas, making these very promising targets.

第1阶段的主要目标旨在开发重新配置和重新分配的基本算法方法，并通过与其他更具应用的项目进行实践合作，以确保它们有用并适合CCC的整体目标。这是通过考虑在不同信息和优化量表上工作的方法（例如，通过数学编程的确切全局计算，通过本地方法进行的启发式方法进行逐渐改进的方法），不同的时间尺度（例如，在离线设置中应用于在线方案，以及范围范围的范围/querversive contry/quorcorsing contry/quorcossing scorme consersing/quorcocsed scormess，compocsess的范围更加耗时，并且集中计算与游戏理论机理设计）。这些量表通常是链接的（例如，分散的计算可能与有限的信息相关），而无需在方法上等效（例如，即使在集中式的方案中，在有限的信息下进行优化，也会产生在线算法的领域）。 A general approach in the field of algorithmics is to develop separate methods for scenarios at different scales, i.e., to consider one combination of the described scales, and develop powerful methods that work well under these specific conditions.The main overall objective for Phase 2 is to overcome this limitation and study of multi-scale, integrated and interleaving methods for complex scenarios, in which these different scales (information and optimization, time, computation) are not treated separately,但以互换和平行的方式使用。这需要将单独的算法方法融合到多尺度方法中，在B1中进行，与分布式合同的概念方法和技术和算法设计和工作的概念方法和技术与其他项目的合作，以及与其他项目的整体相结合，与其他项目的整合在案例研究中的整合方法中进行了构成的概念方法和技术和工作。最值得注意的是，这些涉及研究机器人平台和自动驾驶汽车，两者都会在一个机器人或车辆中组织资源分配以及在协调多个平台时，这两者都带来了相关的科学挑战。除了我们的算法专业知识之外，我们在两个应用领域都有丰富的经验，使这些非常有前途的目标成为现实。

项目成果

Cost-Oblivious Reallocation for Scheduling and Planning

用于调度和规划的成本无关的重新分配

• DOI: 10.1145/2755573.2755589
• 发表时间: 2015
• 期刊: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures
• 作者: M.E. Bender;M. Farach-Colton;S.P. Fekete;J. Fineman;S. Gilbert
• 通讯作者: S. Gilbert

A competitive strategy for distance-aware online shape allocation

距离感知在线形状分配的竞争策略

• DOI: 10.1016/j.tcs.2014.02.050
• 发表时间: 2014
• 期刊: Theor. Comput. Sci.
• 作者: S.P. Fekete;J.-M. Reinhardt;N. Schweer
• 通讯作者: N. Schweer

Conflict-Free Coloring of Graphs

图形的无冲突着色

• DOI: 10.1137/17m1146579
• 发表时间: 2018
• 期刊: SIAM J. Discret. Math.
• 作者: Z. Abel;V. Alvarez;E.D. Demaine;S. Fekete;A. Gour;A. Hesterberg;P. Keldenich;C. Scheffer
• 通讯作者: C. Scheffer

Resource-efficient dynamic partial reconfiguration on FPGAs for space instruments

• DOI: 10.1109/ahs.2017.8046355
• 发表时间: 2017-07
• 期刊: 2017 NASA/ESA Conference on Adaptive Hardware and Systems (AHS)
• 作者: A. Dörflinger;B. Fiethe;H. Michalik;S. Fekete;Phillip Keldenich;Christian Scheffer

An efficient data structure for dynamic two-dimensional reconfiguration

一种用于动态二维重构的高效数据结构

• DOI: 10.1016/j.sysarc.2017.02.004
• 发表时间: 2017
• 期刊: ArXiv
• 作者: S.P. Fekete;J.-M. Reinhardt;C. Scheffer
• 通讯作者: C. Scheffer