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 item with some profit and weight is placed. An agent seeks to collect a subset of the items. To do so, the agent must decide which items to collect and to determine a cyclic tour visiting the corresponding locations. While collecting an item yields its profit as a reward, the agent’s speed decreases as more weight is picked up. The problem involves two competing objectives: maximizing the total profit of the collected items and minimizing the travel time of the tour. While many heuristics and exact algorithms (with a non-polynomial running time) have been developed, no approximation algorithms are known for any variant of the TTP. We aim at computing an (α₁,α₂)-approximate Pareto set that, for every solution, contains another solution collecting at least a 1/(α₁) fraction of its profit while requiring at most α₂ times its travel time. Our main result is an algorithm that calculates a (9 + ε,9 + ε)-approximate Pareto set in polynomial time. We also consider the setting in which the set of items to be collected is given in advance, so that the agent only has to compute a tour through the corresponding locations that minimizes the total travel time. This is the so-called Weighted TSP. For this setting, we present a (2e + ε)-approximation algorithm.

Connected clustering denotes a family of constrained clustering problems in which we are given a distance metric and an undirected connectivity graph G that can be completely unrelated to the metric. The aim is to partition the n vertices into a given number k of clusters such that every cluster forms a connected subgraph of G and a given clustering objective gets minimized. The constraint that the clusters are connected has applications in many different fields, like for example community detection and geodesy. So far, k-center and k-median have been studied in this setting. It has been shown that connected k-median is Ω(n^{1- ε})-hard to approximate which also carries over to the connected k-means problem, while for connected k-center it remained an open question whether one can find a constant approximation in polynomial time. We answer this question by providing an Ω(log^*(k))-hardness result for the problem. Given these hardness results, we study the problems on graphs with bounded treewidth. We provide exact algorithms that run in polynomial time if the treewidth w is a constant. Furthermore, we obtain constant approximation algorithms that run in FPT time with respect to the parameter max(w,k). Additionally, we consider the min-sum-radii (MSR) and min-sum-diameter (MSD) objectives. We prove that on general graphs, connected MSR can be approximated with an approximation factor of (3 + ε) and connected MSD with an approximation factor of (4 + ε). The latter also directly improves the best known approximation guarantee for unconstrained MSD from (6 + ε) to (4 + ε). We complement this with a reduction showing that connected MSR is NP-hard to approximate with an approximation factor smaller than (4/3).

As a major unsupervised learning method, clustering has received a lot of attention over multiple decades. The various clustering problems that have been studied intensively include, e.g., the $k$-means problem and the $k$-center problem. However, in applications, it is common that good clusterings should optimize multiple objectives (e.g., visualizing data on a map by clustering districts into areas that are both geographically compact but also homogeneous with respect to the data). We study combinations of different objectives, for example optimizing $k$-center and $k$-means simultaneously or optimizing $k$-center with respect to two different metrics. Usually these objectives are conflicting and cannot be optimized simultaneously, making it necessary to find trade-offs. We develop novel algorithms for computing the set of Pareto-optimal solutions (approximately) for various combinations of two objectives. Our algorithms achieve provable approximation guarantees and we demonstrate in several experiments that the (approximate) Pareto set contains good clusterings that cannot be found by considering one of the objectives separately.

Abstract Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem. The former problem has been introduced by Ge et al. (ACM Trans Knowl Discov Data 2(2):1–35, 2008. https://doi.org/10.1145/1376815.1376816 ) to model clustering of data sets with both attribute and relationship data. These problems arise from the classical k-center and k-diameter problems by adding a side constraint. For the side constraint, we are given an undirected connectivity graphG on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in G. Usually in clustering problems one assumes that the clusters are pairwise disjoint. We study this case but additionally also the case that clusters are allowed to be non-disjoint. This can help to satisfy the connectivity constraints. Our main result is an $$O(\log ^2k)$$ O ( log 2 k ) -approximation algorithm for the disjoint connected k-center and k-diameter problem. For Euclidean spaces of constant dimension and for metrics with constant doubling dimension, the approximation factor improves to O(1). Our algorithm works by computing a non-disjoint connected clustering first and transforming it into a disjoint connected clustering. We complement these upper bounds by several upper and lower bounds for variations and special cases of the model.

Motivated by an application from geodesy, we introduce a novel clustering problem which is a $k$-center (or k-diameter) problem with a side constraint. For the side constraint, we are given an undirected connectivity graph $G$ on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in $G$. We call the resulting problems the connected $k$-center problem and the connected $k$-diameter problem. We prove several results on the complexity and approximability of these problems. Our main result is an $O(\log^2{k})$-approximation algorithm for the connected $k$-center and the connected $k$-diameter problem. For Euclidean metrics and metrics with constant doubling dimension, the approximation factor of this algorithm improves to $O(1)$. We also consider the special cases that the connectivity graph is a line or a tree. For the line we give optimal polynomial-time algorithms and for the case that the connectivity graph is a tree, we either give an optimal polynomial-time algorithm or a $2$-approximation algorithm for all variants of our model. We complement our upper bounds by several lower bounds.

The k-means++ algorithm due to Arthur and Vassilvitskii [David Arthur and Sergei Vassilvitskii, 2007] has become the most popular seeding method for Lloyd’s algorithm. It samples the first center uniformly at random from the data set and the other k-1 centers iteratively according to D²-sampling, i.e., the probability that a data point becomes the next center is proportional to its squared distance to the closest center chosen so far. k-means++ is known to achieve an approximation factor of 𝒪(log k) in expectation. Already in the original paper on k-means++, Arthur and Vassilvitskii suggested a variation called greedy k-means++ algorithm in which in each iteration multiple possible centers are sampled according to D²-sampling and only the one that decreases the objective the most is chosen as a center for that iteration. It is stated as an open question whether this also leads to an 𝒪(log k)-approximation (or even better). We show that this is not the case by presenting a family of instances on which greedy k-means++ yields only an Ω(𝓁⋅log k)-approximation in expectation where 𝓁 is the number of possible centers that are sampled in each iteration. Inspired by the negative results, we study a variation of greedy k-means++ which we call noisy k-means++ algorithm. In this variation only one center is sampled in every iteration but not exactly by D²-sampling. Instead in each iteration an adversary is allowed to change the probabilities arising from D²-sampling individually for each point by a factor between 1-ε₁ and 1+ε₂ for parameters ε₁ ∈ [0,1) and ε₂ ≥ 0. We prove that noisy k-means++ computes an 𝒪(log² k)-approximation in expectation. We use the analysis of noisy k-means++ to design a moderately greedy k-means++ algorithm.

Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A.