4 papers · 1 filter
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…
Approximation Ineffectiveness of a Tour-Untangling Heuristic
Bodo Manthey, Jesse van Rhijn
We analyze a tour-uncrossing heuristic for the Travelling Salesperson Problem, showing that its worst-case approximation ratio is and its average-case approximation ratio is…
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP
Bodo Manthey, Jesse van Rhijn
The 2-opt heuristic is a simple local search heuristic for the Travelling Salesperson Problem (TSP). Although it usually performs well in practice, its worst-case running time is p…
Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP
Bodo Manthey, Jesse van Rhijn
We analyze simulated annealing (SA) for simple randomized instances of the Traveling Salesperson Problem. Our analysis shows that the theoretically optimal cooling schedule of Haje…