Jan Eube

Jan Eube, Kelin Luo, Aneta Neumann et al.

The Traveling Thief Problem (TTP) is a multi-component optimization problem that captures the interplay between routing and packing decisions by combining the classical Traveling Salesperson Problem (TSP) and the Knapsack Problem (KP). The TTP has gained significant attention in the evolutionary computation literature and a wide range of approaches have been developed over the last 10 years. Judging the performance of these algorithms in particular in terms of how close the get to optimal solutions is a very challenging task as effective exact methods are not available due to the highly challenging traveling component. In this paper, we study the tour-optimization component of TTP under a fixed packing plan. We formulate this task as a weighted variant of the TSP, where travel costs depend on the cumulative weight of collected items, and investigate how different distance metrics and cost functions affect computational complexity. We present an $(O(n^2))$-time dynamic programming algorithm for the path metric with general cost functions, prove that the problem is NP-hard even on a star metric, and develop constant-factor approximation algorithms for star metrics. Finally, we also develop an approximation algorithm for the problem under a general metric with a linear cost function. We complement our theoretical results with experimental evaluations on standard TTP instances adjusted to a path metric. Our experimental results demonstrate the practical effectiveness of our approaches by comparing it to solutions produced by popular iterative search algorithms. The results show that our methods are able to significantly improve the quality of solutions for some benchmark instances by optimizing the traveling part while pointing out the optimality of the travel component for other solutions obtained by iterative search methods.

Anup Bhattacharya, Jan Eube, Heiko Röglin et al.

The k-means++ algorithm due to Arthur and Vassilvitskii 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^2$-sampling where 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 $O(\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^2$-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 $O(\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 $Ω(\ell\cdot \log k)$-approximation in expectation where $\ell$ is the number of possible centers that are sampled in each iteration. We also study a variation, which we call noisy k-means++ algorithm. In this variation only one center is sampled in every iteration but not exactly by $D^2$-sampling anymore. Instead in each iteration an adversary is allowed to change the probabilities arising from $D^2$-sampling individually for each point by a factor between $1-ε_1$ and $1+ε_2$ for parameters $ε_1 \in [0,1)$ and $ε_2 \ge 0$. We prove that noisy k-means++ compute an $O(\log^2 k)$-approximation in expectation. We also discuss some applications of this result.