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

In the over 40 years since the beginning of Computational Geometry, a widerange of optimization problems have been proposed and investigated bycomputational geometers, mainly from a theoretical point of view. Many of thosetasks belong to the NP-hard class of problems, for which the existence ofpolynomial-time algorithms implies P=NP. While Computational Geometry hasconsidered a wide spectrum of NP-hard optimization problems, positive resultstypically imply polynomial-time, constant-factor approximation algorithms,without much regard for practical solution quality, realistic running times, oreven exact solutions. In principle, this is the approach taken by therelatively new area of Algorithm Engineering; however, the impact on hardproblems treated in the community of Computational Geometry has been ratherlimited, as the focus has been more on streamlining theoretical computationalcomplexity, rather than exact methods.This seam between separate successful areas is precisely where our projectintends to bring new contributions, making use of methods from CombinatorialOptimization, based on the recognized expertise in all three areas. At theconcrete level, we will study a selection of different, natural geometricoptimization problems that have enjoyed attention from the perspective ofComputational Geometry, but are still lacking practical approaches to computingprovably optimal or near-optimal solutions. This involves applying tools andtechniques from Combinatorial Optimization and Algorithm Engineering to solveproblems from Computational Geometry, but also algorithmic methods fromComputational Geometry itself. For these problems, we will providecomputational results, based on benchmark instances and solution methods thatcan serve as reference points, both for specific instances (for which we willprovide provably optimal or near-optimal solutions), as well as for particularalgorithmic approaches (for which we will provide practical experiments that gobeyond worst-case bounds). At the general level, we will develop generic toolsand methods for solving geometric optimization problems with practically usefulperformance, by making use of sparsification techniques to get good solutionsto very large instances, for dealing with inaccurate data and error analysis,and for generally modeling, developing and testing. Moreover, we will establishan integrated platform that provides an overall toolbox, a benchmark andresults repository, and a challenge site.In recent months, we have managed to demonstrate the promise of our approach byestablishing and successfully running an annual Computational GeometryChallenge, based on specific problems of this type, indicating the potentialfor changing the scope of a theory-oriented field towards practical usefulnessfor challenging problems.

• DFG Programme: Research Grants
• International Connection: Israel, USA
• Cooperation Partners: Professor Erik Demaine, Ph.D.; Professor Dr. Dan Halperin; Professor Dr. Joseph S. B. Mitchell