Showing cs.DSShow all
3 papers · 1 filter
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…
cs.DS2023
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…