15 citations · 35 across the 19 of their papers we have counts for
22 papers
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise
Marvin Künnemann, Bodo Manthey, Rianne Veenstra
The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of…
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…
Probabilistic Analysis of Facility Location on Random Shortest Path Metrics
Stefan Klootwijk, Bodo Manthey
The facility location problem is an NP-hard optimization problem. Therefore, approximation algorithms are often used to solve large instances. Such algorithms often perform much be…
Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics
Stefan Klootwijk, Bodo Manthey, Sander K. Visser
Simple heuristics often show a remarkable performance in practice for optimization problems. Worst-case analysis often falls short of explaining this performance. Because of this,…