research
∙
09/19/2023
Worst-Case and Smoothed Analysis of Hartigan's Method for k-Means Clustering
We analyze the running time of Hartigan's method, an old algorithm for t...
share
research
∙
02/22/2023
Approximation Ineffectiveness of a Tour-Untangling Heuristic
We analyze a tour-uncrossing heuristic for the Travelling Salesperson Pr...
research
∙
11/30/2022
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP
The 2-opt heuristic is a simple local search heuristic for the Travellin...
research
∙
08/24/2022
Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP
We analyze simulated annealing (SA) for simple randomized instances of t...
research
∙
12/06/2021