4 papers
Convergence and Running Time of Time-dependent Ant Colony Algorithms
Bodo Manthey, Jesse van Rhijn, Ashkan Safari +1
Ant Colony Optimization (ACO) is a well-known method inspired by the foraging behavior of ants and is extensively used to solve combinatorial optimization problems. In this paper,…
Counting Locally Optimal Tours in the TSP
Bodo Manthey, Jesse van Rhijn
We show that the problem of counting the number of 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show…
Complexity of Local Search for Euclidean Clustering Problems
Bodo Manthey, Nils Morawietz, Jesse van Rhijn +1
We show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-complete. First, we show that the Hartigan--Wong method for -Means cluste…
Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
Bodo Manthey, Jesse van Rhijn
We analyze the running time of the Hartigan-Wong method, an old algorithm for the -means clustering problem. First, we construct an instance on the line on which the method can…