A2: Approximation Algorithms for Clustering, Aggregation and Simplification under Side Constraints

PI: Melanie Schmidt

Summary

This project focuses on the aspect of side constraints in the context of clustering, aggregation and simplification problems from geodesy and on the question to what extend it is possible to efficiently find approximative solutions for constrained problems. Side constraints occur naturally both in the process of digitally designing maps and in sea surface representation.

Clustering problems as studied in combinatorial optimization are often NP-hard even without side constraints, i.e., it is most likely not possible to solve them optimally in polynomial time. Typical solutions for this are to use ILP formulations and speed up (exponential-time) algorithms in practice, or to design application specific heuristics. An alternative are approximation algorithms: These aim to find solutions with a provable worst-case guarantee in polynomial time. For classical clustering algorithms, there exists a large variety of approximation algorithms.

Although clustering problems arising in geodesy are often related to those clustering problems that are studied extensively in the theory and algorithms community, they differ in important aspects: a) They involve many side constraints and b) the input objects can be complex objects like polygons, graphs or time series. In this project, we aim to advance the state-of-the-art for approximation problems for clustering of complex geometric objects under side constraints.