33 citations · 53 across the 12 of their papers we have counts for
18 papers
Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy
Johanna Hillebrand, Jan Höckendorff, Jürgen Kusche +5
Constrained optimization extends classical optimization by integrating side information, making it widely applicable across scientific and engineering domains. Consider a setting w…
Finding Regions of Maximum Circularity in Plane Geometric Graphs
Jan-Henrik Haunert, Joshua Marc Könen, Heiko Röglin +1
A problem that occurs in different applications in geographical information science is to generate compact regions from areas on a map. This is important, e.g., in the context of e…
Approximation Algorithms for the Traveling Thief Problem
Jan Eube, Kelin Luo, Heiko Röglin +1
The Traveling Thief Problem (TTP) combines the Traveling Salesperson Problem with the Knapsack Problem. In this problem, a finite metric space is given, and at each location an ite…
On the number of iterations of the DBA algorithm
Frederik Brüning, Anne Driemel, Alperen Ergür +1
The DTW Barycenter Averaging (DBA) algorithm is a widely used algorithm for estimating the mean of a given set of point sequences. In this context, the mean is defined as a point s…
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
Matthias Englert, Heiko Röglin, Berthold Vöcking
2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on real world Euclidean instances both with respect to running t…
Connected k-Center and k-Diameter Clustering
Lukas Drexler, Jan Eube, Kelin Luo +4
Motivated by an application from geodesy, we introduce a novel clustering problem which is a -center (or k-diameter) problem with a side constraint. For the side constraint, we…
Minimum-Error Triangulations for Sea Surface Reconstruction
Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert +6
We apply state-of-the-art computational geometry methods to the problem of reconstructing a time-varying sea surface from tide gauge records. Our work builds on a recent article by…
Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering
Carsten Fischer, Heiko Röglin
In the bin covering problem, the goal is to fill as many bins as possible up to a certain minimal level with a given set of items of different sizes. Online variants, in which the…
New Deterministic Algorithms for Solving Parity Games
Matthias Mnich, Heiko Röglin, Clemens Rösner
We study parity games in which one of the two players controls only a small number of nodes and the other player controls the other nodes of the game. Our main result is…
The Alternating Stock Size Problem and the Gasoline Puzzle
Alantha Newman, Heiko Röglin, Johanna Seif
Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that: (i) all prefix sums of the ordering are nonnegative, and (ii…
Smoothed Analysis of the Successive Shortest Path Algorithm
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey +2
The minimum-cost flow problem is a classic problem in combinatorial optimization with various applications. Several pseudo-polynomial, polynomial, and strongly polynomial algorithm…
Solving Totally Unimodular LPs with the Shadow Vertex Algorithm
Tobias Brunsch, Anna Großwendt, Heiko Röglin
We show that the shadow vertex simplex algorithm can be used to solve linear programs in strongly polynomial time with respect to the number of variables, the number of con…
Efficient Clustering with Limited Distance Information
Konstantin Voevodski, Maria-Florina Balcan, Heiko Roglin +2
Given a point set S and an unknown metric d on S, we study the problem of efficiently partitioning S into k clusters while querying few distances between the points. In our model w…
Improved Smoothed Analysis of Multiobjective Optimization
Tobias Brunsch, Heiko Röglin
We present several new results about smoothed analysis of multiobjective optimization problems. Motivated by the discrepancy between worst-case analysis and practical experience, t…
Smoothed Performance Guarantees for Local Search
Tobias Brunsch, Heiko Röglin, Cyriel Rutten +1
We study popular local search and greedy algorithms for scheduling. The performance guarantee of these algorithms is well understood, but the worst-case lower bounds seem somewhat…
Clustering Protein Sequences Given the Approximation Stability of the Min-Sum Objective Function
Konstantin Voevodski, Maria-Florina Balcan, Heiko Roglin +2
We study the problem of efficiently clustering protein sequences in a limited information setting. We assume that we do not know the distances between the sequences in advance, and…
Lower Bounds for the Smoothed Number of Pareto optimal Solutions
Tobias Brunsch, Heiko Roeglin
In 2009, Roeglin and Teng showed that the smoothed number of Pareto optimal solutions of linear multi-criteria optimization problems is polynomially bounded in the number of va…
Efficient Clustering with Limited Distance Information
Konstantin Voevodski, Maria-Florina Balcan, Heiko Roglin +2
Given a point set S and an unknown metric d on S, we study the problem of efficiently partitioning S into k clusters while querying few distances between the points. In our model w…