3 papers
cs.CC2025
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…
cs.DS2025
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,…
cs.DS2024
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…