Abstract 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)$$ Θ ( log n ) , leaving a gap to the best-known lower bound of $$\Omega (\sqrt{\log n})$$ Ω ( 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)$$ 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 )$$ ( 1 + ε ) -competitive and reassigns any request at most $$O(\frac{1}{\varepsilon ^2})$$ O ( 1 ε 2 ) times. This special case is particularly noteworthy, as a lower bound of $$\Omega (\log n)$$ Ω ( log n ) , constructed using such instances, applies to a broad class of online algorithms, including all deterministic algorithms studied in the literature.

Exploring unknown environments is a fundamental task in many domains, e.g., robot navigation, network security, and internet search. We initiate the study of a learning-augmented variant of the classical, notoriously hard online graph exploration problem by adding access to machine-learned predictions. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm and significantly outperforms any known online algorithm if the prediction is of high accuracy while maintaining good guarantees when the prediction is of poor quality. We provide theoretical worst-case bounds that gracefully degrade with the prediction error, and we complement them by computational experiments that confirm our results. Further, we extend our concept to a general framework to robustify algorithms. By interpolating carefully between a given algorithm and NN, we prove new performance bounds that leverage the individual good performance on particular inputs while establishing robustness to arbitrary inputs.

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.

Knapsack problems are among the most fundamental problems in optimization. In the Multiple Knapsack problem, we are given multiple knapsacks with different capacities and items with values and sizes. The task is to find a subset of items of maximum total value that can be packed into the knapsacks without exceeding the capacities. We investigate this problem and special cases thereof in the context of dynamic algorithms and design data structures that efficiently maintain near-optimal knapsack solutions for dynamically changing input. More precisely, we handle the arrival and departure of individual items or knapsacks during the execution of the algorithm with worst-case update time polylogarithmic in the number of items. As the optimal and any approximate solution may change drastically, we only maintain implicit solutions and support certain queries in polylogarithmic time, such as the packing of an item and the solution value. While dynamic algorithms are well-studied in the context of graph problems, there is hardly any work on packing problems and generally much less on non-graph problems. Given the theoretical interest in knapsack problems and their practical relevance, it is somewhat surprising that Knapsack has not been addressed before in the context of dynamic algorithms and our work bridges this gap.

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 [S. Raghvendra, 2018] achieves a competitive factor of Θ(log n). This result matches a lower bound of Ω(log n) [A. Antoniadis et al., 2018] 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, i.e., we allow to reassign previously matched edges. We show an O(1)-competitive algorithm for online matching on the line with amortized recourse of O(log n). 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+ε)-competitive algorithm that reassigns any request at most O(ε^{-1.001}) times. This special case is interesting as the aforementioned quite general lower bound Ω(log n) holds for such instances.

We consider the problem of computing a Steiner tree of minimum cost under a k-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 of 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.

In the Anchored Rectangle Packing (ARP) problem, we are given a set of points P in the unit square [0,1]^2 and seek a maximum-area set of axis-aligned interior-disjoint rectangles S, each of which is anchored at a point p in P. In the most prominent variant - Lower-Left-Anchored Rectangle Packing (LLARP) - rectangles are anchored in their lower-left corner. Freedman [W. T. Tutte (Ed.), 1969] conjectured in 1969 that, if (0,0) in P, then there is a LLARP that covers an area of at least 0.5. Somewhat surprisingly, this conjecture remains open to this day, with the best known result covering an area of 0.091 [Dumitrescu and Tóth, 2015]. Maybe even more surprisingly, it is not known whether LLARP - or any ARP-problem with only one anchor - is NP-hard. In this work, we first study the Center-Anchored Rectangle Packing (CARP) problem, where rectangles are anchored in their center. We prove NP-hardness and provide a PTAS. In fact, our PTAS applies to any ARP problem where the anchor lies in the interior of the rectangles. Afterwards, we turn to the LLARP problem and investigate two different resource-augmentation settings: In the first we allow an epsilon-perturbation of the input P, whereas in the second we permit an epsilon-overlap between rectangles. For the former setting, we give an algorithm that covers at least as much area as an optimal solution of the original problem. For the latter, we give an (1 - epsilon)-approximation.