15 citations · 35 across the 19 of their papers we have counts for
19 papers · 1 filter
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,…
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm
Kamiel Cornelissen, Bodo Manthey
The minimum-cost flow (MCF) problem is a fundamental optimization problem with many applications and seems to be well understood. Over the last half century many algorithms have be…
Smoothed Analysis of the Successive Shortest Path Algorithm
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey +2
The minimum-cost flow problem is a classic problem in combinatorial optimization with various applications. Several pseudo-polynomial, polynomial, and strongly polynomial algorithm…
Probabilistic Analysis of Power Assignments
Maurits de Graaf, Bodo Manthey
A fundamental problem for wireless ad hoc networks is the assignment of suitable transmission powers to the wireless devices such that the resulting communication graph is connecte…
Approximability of Connected Factors
Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey +2
Finding a d-regular spanning subgraph (or d-factor) of a graph is easy by Tutte's reduction to the matching problem. By the same reduction, it is easy to find a minimal or maximal…
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey +1
Belief propagation (BP) is a message-passing heuristic for statistical inference in graphical models such as Bayesian networks and Markov random fields. BP is used to compute margi…
On Smoothed Analysis of Quicksort and Hoare's Find
Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey +1
We provide a smoothed analysis of Hoare's find algorithm and we revisit the smoothed analysis of quicksort. Hoare's find algorithm - often called quickselect - is an easy-to-implem…
k-Means has Polynomial Smoothed Complexity
David Arthur, Bodo Manthey, Heiko Röglin
The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential wors…
Improved Smoothed Analysis of the k-Means Method
Bodo Manthey, Heiko Röglin
The k-means method is a widely used clustering algorithm. One of its distinguished features is its speed in practice. Its worst-case running-time, however, is exponential, leaving…
Approximating Multi-Criteria Max-TSP
Markus Bläser, Bodo Manthey, Oliver Putz
We present randomized approximation algorithms for multi-criteria Max-TSP. For Max-STSP with k > 1 objective functions, we obtain an approximation ratio of $1/k - \eps$ for arbitra…
On Approximating Multi-Criteria TSP
Bodo Manthey
We present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP). First, we devise randomized approximation algorithms for multi-c…
Minimum-weight Cycle Covers and Their Approximability
Bodo Manthey
A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set…
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems
Bodo Manthey, L. Shankar Ram
In multi-criteria optimization problems, several objective functions have to be optimized. Since the different objective functions are usually in conflict with each other, one cann…
Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
Bodo Manthey
A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set…