Approximation Algorithms for Geometric Data Analysis and Their Practicability

• Applicant: Professorin Dr. Melanie Schmidt
• Subject Area: Theoretical Computer Science
• Term: since 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 456558332

Geometric data analysis is an emerging field on the intersection of computational geometry and machine learning that is concerned with the analysis of data that has geometric properties. Algorithmic data analysis is a term that is being established for designing methods for data analysis by using techniques from the areas of algorithms, theory or algorithm engineering. In this project we are interested in algorithmic geometric data analysis, or, more precisely, in approximation algorithms for geometric data analysis tasks. The focus is on finding algorithms with provable performance guarantees, and on translating them into methods that are practically efficient from the view point of algorithm engineering. We are also interested in inapproximability results which bound the limits of what can be achieved.Data analysis tasks are often very difficult to solve, involve side constraints or have a complicated combinatorial structure. They are thus often approached with heuristics that are evaluated on specific data. These have no guarantee on the worst-case performance. Sometimes, when heuristics provide poor results or high quality is of major importance, exact algorithms are used, in particular based on integer linear programs that can be solved by standard solvers. These approaches take exponential worst-case time and are also often not very fast in practice.Approximation algorithms offer an alternative: They are efficient (at least in theory) and provide a provable bound on the worst quality produced. Approximation algorithms are particularly interesting for solving data analysis tasks in practice if they are also practically efficient and provide high quality results (often much better than their theoretical guarantee). The area of practical approximation algorithms for data analysis tasks has gained a lot of popularity lately.The geometric data analysis tasks that we want to study in this project are mainly from the area of clustering, with a focus on the very important k-means problem. For the k-means problem, the gap between theoretical results and practically used algorithms is narrowing and there is a real chance to close it. Aside from k-means, we want to study other clustering problems, but also connections between clustering and further geometric data analysis tasks. Interesting connections for example exist between clustering and trajectory analysis, and between clustering and geometric network design problems. Our aim is to improve the state-of-the-art of approximation algorithms for geometric data analysis problems from a theory perspective, but also to design practically efficient approximation algorithms which we also want to implement and test.

• DFG Programme: Independent Junior Research Groups