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.
The following theses were completed within the scope of this project:
| Name | Title | Semester |
| Luka Lukatela | On the route-preserving road network generalization problem (Master's Thesis) | Winter 22/23 |
| Erik Vaihinger | Identifikation meteorologischer Blocking Events mithilfe von Graphenalgorithmen (Bachelor's Thesis) | Summer 24 |
| Johanna Hillebrand | Geographically Coherent Clusterings of Tide Gauge Stations based on Time Series with Missing Data (Master's Thesis) | Summer 24 |
| Marcel Hielscher | Connected Clustering für allgemeine Nachbarschaftsgraphen (Master's Thesis) | Winter 24/25 |
| Julius Mann | Connected Clustering auf zweizeiligen Gittergraphen (Bachelor's Thesis) | Winter 24/25 |
| Yahya Versic | Algorithmische Analyse des Polygonclusteringproblems mit Nebenbedingungen (Bachelor's Thesis) | Winter 24/25 |
| Valentin Pukhov | Polynomielle exakte Algorithmen für eindimensionales k-center mit einer Nebenbedingung (Bachelor's Thesis) | Winter 25/26 |
| Dominik Wierich | Approximationsalgorithmen für gewichtetes k-center Clustering mit unteren Schranken (Bachelor's Thesis) | Winter 25/26 |
| Johannes Scholl | Evaluation einer Anonymisierungsmethode für Trajektorien (Bachelor's Thesis) | Winter 25/26 |
| David Birgel | Ein algorithmischer Ansatz zur Rekonstruktion unvollständiger ozeanographischer Felder mittels empirischer orthogonaler Funktionen (Bachelor's Thesis) | Winter 25/26 |
| Robin Wiebus | Inkrementelles eindimensionales Clustering (Bachelor's Thesis) | Summer 26 |
| Niklas Brinkmann | Rekonstruktion von Meerestemperaturdaten mit DINEOF: Evaluierung bei verschiedenen Lückenmustern und Wolkenszenarien (Bachelor's Thesis) | Summer 26 |
| Tim Urban | Global Sea Level Reconstruction Using Reduced Space Optimal Interpolation: Reproduction, Validation and Modifications (Master's Thesis) | Winter 26/27 |