Computational Geometry: Solving Hard Optimization Problems (CG:SHOP)

• Applicant: Professor Dr. Sándor Fekete
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 444569951

The objective of our project CG:SHOP (Computational Geometry: Solving Hard Optimization Problems) is to develop practically useful methods for solving hard geometric optimization problems. This is based on the fundamental insight that focusing solely on theoretical complexity misses an important point: The existence of algorithms with an asymptotic worst-case running time bounded by a polynomial is neither sufficient nor necessary for computing practically useful solutions that are provably optimal or near optimal. To this end, we develop methods for combining theoretical approaches from Computational Geometry and Mathematical Optimization with practical techniques from Algorithm Engineering to achieve provably good solutions for instances of practically interesting sizes for difficult problems of practical relevance. In particular, we have considered a variety of specific geometric optimization problems dealing with (A) Covering and Dispersion, (B) Structure Problems, and (C) Touring Problems, as well as more generic aspects of (D) Sparsification Techniques, (E) Errors and Objectives, and (F) Toolbox and Library. The first phase of our project has been a resounding success, leading to 15 publications that cover all aspects of our ambitious work program, with another 4 currently under review and 2 in preparation. In addition, we have succeeded in establishing a special track (”The CG:SHOP Challenge”) at the world-leading Symposium on Computational Geometry (SoCG) to deal with the practical solution of geometric optimization problems. This has led to 25 further publications, with several more in preparation. This success makes it possible and desirable to extend and refine our work. As before, we will study a number of specific problem areas in (G) Advanced Structure Problems, (H) Advanced Touring Problems, (I) Packing Problems, as well as pursue more universal methods and perspectives of (J) Analyzing Neighborhood Structures, (K) Instance Space Analysis and AI, and (L) Challenges and Community Building.

• DFG Programme: Research Grants
• International Connection: Israel, USA
• Cooperation Partners: Professor Dr. Aaron T. Becker; Professorin Dr. Erin Chambers; Professor Dr. Dan Halperin; Professor Dr. Joseph S. B. Mitchell