LNLukas Nölke
Lukas Nölke
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Lukas Nölke has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Nicole Megow
University of Bremen, Bremen, Germany
6 shared publications - Bertrand Simon
IN2P3 Computing Center CNRS Villeurbanne France
3 shared publications - Ruben Hoeksma
University of Twente
3 shared publications - Franziska Eberle
London School of Economics and Political Science
2 shared publications - Kevin Schewior
Department of Mathematics and Computer Science University of Cologne Germany
2 shared publications Martin Böhm
Institute of Computer Science University of Wrocław Poland
2 shared publications
Latest Publications
- Open Access
- 1 March 2025
- Published by Springer Nature in Algorithmica
- Vol. 87 (6) , 813-841
Online Metric Matching on the Line with Recourse
In online metric matching on the line, n requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all located on the real line. The goal is to minimize the sum of distances between the requests and their assigned servers. The best known online algorithm achieves a competitive ratio of $$\Theta (\log n)$$ , leaving a gap to the best-known lower bound of $$\Omega (\sqrt{\log n})$$ . In this work, we approach the problem in a recourse model where online decisions can be partially revised, allowing for the reassignment of previously matched edges. In contrast to the traditional online setting, we show that with an amortized recourse budget of $$O(\log n)$$ , we can obtain an O(1)-competitive algorithm for online metric matching on the line. This is one of the first non-trivial results for metric matching with recourse. Additionally, for so-called alternating instances, where no more than one request lies between two servers, we achieve a near-optimal result. Specifically, we give a simple algorithm that is $$(1+\varepsilon )$$ -competitive and reassigns any request at most $$O(\frac{1}{\varepsilon ^2})$$ times. This special case is particularly noteworthy, as a lower bound of $$\Omega (\log n)$$ , constructed using such instances, applies to a broad class of online algorithms, including all deterministic algorithms studied in the literature.- 1 March 2025
- Published by Springer Nature in Algorithmica
- Vol. 87 (6) , 813-841
Open AccessOnline Metric Matching on the Line with Recourse
In online metric matching on the line, n requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all located on the real line. The goal is to minimize the sum of distances between the requests and their assigned servers. The best known online algorithm achieves a competitive ratio of $$\Theta (\log n)$$ , leaving a gap to the best-known lower bound of $$\Omega (\sqrt{\log n})$$ . In this work, we approach the problem in a recourse model where online decisions can be partially revised, allowing for the reassignment of previously matched edges. In contrast to the traditional online setting, we show that with an amortized recourse budget of $$O(\log n)$$ , we can obtain an O(1)-competitive algorithm for online metric matching on the line. This is one of the first non-trivial results for metric matching with recourse. Additionally, for so-called alternating instances, where no more than one request lies between two servers, we achieve a near-optimal result. Specifically, we give a simple algorithm that is $$(1+\varepsilon )$$ -competitive and reassigns any request at most $$O(\frac{1}{\varepsilon ^2})$$ times. This special case is particularly noteworthy, as a lower bound of $$\Omega (\log n)$$ , constructed using such instances, applies to a broad class of online algorithms, including all deterministic algorithms studied in the literature. - Open Access
On Hop-Constrained Steiner Trees in Tree-Like Metrics
We consider the problem of computing a Steiner tree of minimum cost under a hop constraint which requires the depth of the tree to be at most $k$. Our main result is an exact algorithm for metrics induced by graphs with bounded treewidth that runs in time $n^{O(k)}$. For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if $k$ is part of the input. The main result can be used to obtain, in quasi-polynomial time, a near-optimal solution that violates the $k$-hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension and bounded doubling dimension. For non-metric graphs, we rule out an $o(\log n)$-approximation, assuming P$\neq$NP even when relaxing the hop constraint by any additive constant.Open AccessOn Hop-Constrained Steiner Trees in Tree-Like Metrics
We consider the problem of computing a Steiner tree of minimum cost under a hop constraint which requires the depth of the tree to be at most $k$. Our main result is an exact algorithm for metrics induced by graphs with bounded treewidth that runs in time $n^{O(k)}$. For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if $k$ is part of the input. The main result can be used to obtain, in quasi-polynomial time, a near-optimal solution that violates the $k$-hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension and bounded doubling dimension. For non-metric graphs, we rule out an $o(\log n)$-approximation, assuming P$\neq$NP even when relaxing the hop constraint by any additive constant. - 2 July 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 1009-1048
Speed-robust scheduling: sand, bricks, and rocks
- 2 July 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 1009-1048
Speed-robust scheduling: sand, bricks, and rocks
- 1 June 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 36 (2) , 1249-1273
On Hop-Constrained Steiner Trees in Tree-Like Metrics
We consider the problem of computing a Steiner tree of minimum cost under a hop constraint that requires the depth of the tree to be at most $k$. Our main result is an exact algorithm for metrics induced by graphs with bounded treewidth that runs in time $n^{O(k)}$. For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if $k$ is part of the input. The main result can be used to obtain, in quasi-polynomial time, a near-optimal solution that violates the $k$-hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension and bounded doubling dimension. For nonmetric graphs, we rule out an $o(\log n)$-approximation, assuming P$\,\neq\,$NP even when relaxing the hop constraint by any additive constant.- 1 June 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 36 (2) , 1249-1273
On Hop-Constrained Steiner Trees in Tree-Like Metrics
We consider the problem of computing a Steiner tree of minimum cost under a hop constraint that requires the depth of the tree to be at most $k$. Our main result is an exact algorithm for metrics induced by graphs with bounded treewidth that runs in time $n^{O(k)}$. For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if $k$ is part of the input. The main result can be used to obtain, in quasi-polynomial time, a near-optimal solution that violates the $k$-hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension and bounded doubling dimension. For nonmetric graphs, we rule out an $o(\log n)$-approximation, assuming P$\,\neq\,$NP even when relaxing the hop constraint by any additive constant.- Open Access
Speed-Robust Scheduling -- Sand, Bricks, and Rocks
The speed-robust scheduling problem is a two-stage problem where given $m$ machines, jobs must be grouped into at most $m$ bags while the processing speeds of the given $m$ machines are unknown. After the speeds are revealed, the grouped jobs must be assigned to the machines without being separated. To evaluate the performance of algorithms, we determine upper bounds on the worst-case ratio of the algorithm's makespan and the optimal makespan given full information. We refer to this ratio as the robustness factor. We give an algorithm with a robustness factor $2-1/m$ for the most general setting and improve this to $1.8$ for equal-size jobs. For the special case of infinitesimal jobs, we give an algorithm with an optimal robustness factor equal to $e/(e-1) \approx 1.58$. The particular machine environment in which all machines have either speed $0$ or $1$ was studied before by Stein and Zhong (SODA 2019). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of $(1+\sqrt{2})/2 \approx 1.207$. It lays the foundation for an algorithm matching the lower bound of $4/3$ for equal-size jobs.Open AccessSpeed-Robust Scheduling -- Sand, Bricks, and Rocks
The speed-robust scheduling problem is a two-stage problem where given $m$ machines, jobs must be grouped into at most $m$ bags while the processing speeds of the given $m$ machines are unknown. After the speeds are revealed, the grouped jobs must be assigned to the machines without being separated. To evaluate the performance of algorithms, we determine upper bounds on the worst-case ratio of the algorithm's makespan and the optimal makespan given full information. We refer to this ratio as the robustness factor. We give an algorithm with a robustness factor $2-1/m$ for the most general setting and improve this to $1.8$ for equal-size jobs. For the special case of infinitesimal jobs, we give an algorithm with an optimal robustness factor equal to $e/(e-1) \approx 1.58$. The particular machine environment in which all machines have either speed $0$ or $1$ was studied before by Stein and Zhong (SODA 2019). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of $(1+\sqrt{2})/2 \approx 1.207$. It lays the foundation for an algorithm matching the lower bound of $4/3$ for equal-size jobs. - Open Access
On Minimum Generalized Manhattan Connections
We consider minimum-cardinality Manhattan connected sets with arbitrary demands: Given a collection of points $P$ in the plane, together with a subset of pairs of points in $P$ (which we call demands), find a minimum-cardinality superset of $P$ such that every demand pair is connected by a path whose length is the $\ell_1$-distance of the pair. This problem is a variant of three well-studied problems that have arisen in computational geometry, data structures, and network design: (i) It is a node-cost variant of the classical Manhattan network problem, (ii) it is an extension of the binary search tree problem to arbitrary demands, and (iii) it is a special case of the directed Steiner forest problem. Since the problem inherits basic structural properties from the context of binary search trees, an $O(\log n)$-approximation is trivial. We show that the problem is NP-hard and present an $O(\sqrt{\log n})$-approximation algorithm. Moreover, we provide an $O(\log\log n)$-approximation algorithm for complete bipartite demands as well as improved results for unit-disk demands and several generalizations. Our results crucially rely on a new lower bound on the optimal cost that could potentially be useful in the context of BSTs.Open AccessOn Minimum Generalized Manhattan Connections
We consider minimum-cardinality Manhattan connected sets with arbitrary demands: Given a collection of points $P$ in the plane, together with a subset of pairs of points in $P$ (which we call demands), find a minimum-cardinality superset of $P$ such that every demand pair is connected by a path whose length is the $\ell_1$-distance of the pair. This problem is a variant of three well-studied problems that have arisen in computational geometry, data structures, and network design: (i) It is a node-cost variant of the classical Manhattan network problem, (ii) it is an extension of the binary search tree problem to arbitrary demands, and (iii) it is a special case of the directed Steiner forest problem. Since the problem inherits basic structural properties from the context of binary search trees, an $O(\log n)$-approximation is trivial. We show that the problem is NP-hard and present an $O(\sqrt{\log n})$-approximation algorithm. Moreover, we provide an $O(\log\log n)$-approximation algorithm for complete bipartite demands as well as improved results for unit-disk demands and several generalizations. Our results crucially rely on a new lower bound on the optimal cost that could potentially be useful in the context of BSTs. - Open Access
Online Minimum Cost Matching on the Line with Recourse
In online minimum cost matching on the line, $n$ requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all on the real line. The goal is to minimize the sum of distances from the requests to their respective servers. Despite all research efforts, it remains an intriguing open question whether there exists an $O(1)$-competitive algorithm. The best known online algorithm by Raghvendra [SoCG18] achieves a competitive factor of $\Theta(\log n)$. This result matches a lower bound of $\Omega(\log n)$ [Latin18] that holds for a quite large class of online algorithms, including all deterministic algorithms in the literature. In this work we approach the problem in a recourse model where we allow to revoke online decisions to some extent. We show an $O(1)$-competitive algorithm for online matching on the line that uses at most $O(n\log n)$ reassignments. This is the first non-trivial result for min-cost bipartite matching with recourse. For so-called alternating instances, with no more than one request between two servers, we obtain a near-optimal result. We give a $(1+\varepsilon)$-competitive algorithm that reassigns any request at most $O(\varepsilon^{-1.001})$ times. This special case is interesting as the aforementioned quite general lower bound $\Omega(\log n)$ holds for such instances.Open AccessOnline Minimum Cost Matching on the Line with Recourse
In online minimum cost matching on the line, $n$ requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all on the real line. The goal is to minimize the sum of distances from the requests to their respective servers. Despite all research efforts, it remains an intriguing open question whether there exists an $O(1)$-competitive algorithm. The best known online algorithm by Raghvendra [SoCG18] achieves a competitive factor of $\Theta(\log n)$. This result matches a lower bound of $\Omega(\log n)$ [Latin18] that holds for a quite large class of online algorithms, including all deterministic algorithms in the literature. In this work we approach the problem in a recourse model where we allow to revoke online decisions to some extent. We show an $O(1)$-competitive algorithm for online matching on the line that uses at most $O(n\log n)$ reassignments. This is the first non-trivial result for min-cost bipartite matching with recourse. For so-called alternating instances, with no more than one request between two servers, we obtain a near-optimal result. We give a $(1+\varepsilon)$-competitive algorithm that reassigns any request at most $O(\varepsilon^{-1.001})$ times. This special case is interesting as the aforementioned quite general lower bound $\Omega(\log n)$ holds for such instances.