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
∙
08/01/2023
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise
The 2-opt heuristic is a very simple local search heuristic for the trav...
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
∙
03/28/2019
Probabilistic Analysis of Facility Location on Random Shortest Path Metrics
The facility location problem is an NP-hard optimization problem. Theref...
research
∙
10/26/2018