Bodo Manthey

MFCS Conference 2025 Conference Paper

Counting Locally Optimal Tours in the TSP

• Bodo Manthey
• Jesse van Rhijn

We show that the problem of counting 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the TSP on complete graphs is O(1. 2098ⁿ √{n! }). Based on numerical experiments, we conjecture that the true bound is at most O(√{n! }), which is approximately the square root of the total number of tours.

TCS Journal 2021 Journal Article

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, “beyond worst-case analysis” of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained by Bringmann et al. (Algorithmica, 2013), who have used random shortest path metrics constructed using complete graphs to analyze heuristics. The goal of this paper is to generalize these findings to non-complete graphs, especially Erdős–Rényi random graphs. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances, we prove that the greedy heuristic for the minimum distance maximum matching problem, the nearest neighbor and insertion heuristics for the traveling salesman problem, and a trivial heuristic for the k-median problem all achieve a constant expected approximation ratio. Additionally, we show a polynomial upper bound for the expected number of iterations of the 2-opt heuristic for the traveling salesman problem.

TCS Journal 2018 Journal Article

Belief propagation for the maximum-weight independent set and minimum spanning tree problems

• Kamiel Cornelissen
• Bodo Manthey

The belief propagation (BP) algorithm is a message-passing algorithm that is used for solving probabilistic inference problems. In practice, the BP algorithm performs well as a heuristic in many application fields. However, the theoretical understanding of BP is limited. To improve the theoretical understanding of BP, the BP algorithm has been applied to many well-understood combinatorial optimization problems. In this paper, we consider BP applied to the maximum-weight independent set (MWIS) and minimum spanning tree (MST) problems. Sanghavi et al. (2009) [12] applied the BP algorithm to the MWIS problem. We denote their algorithm by BP-MWIS. They showed that if the LP relaxation of the MWIS problem has a unique integral optimal solution and BP-MWIS converges, then BP-MWIS finds the optimal solution. Also, they showed that if the LP relaxation has a non-integral optimal solution, then BP-MWIS does not converge. In this paper, we precisely characterize the graphs for which BP-MWIS is guaranteed to find the optimal solution, regardless of the node weights. Bayati et al. (2008) [2] applied the BP algorithm to the MST problem. We denote their algorithm by BP-MST. They showed that if BP-MST converges, then it finds the optimal solution. In this paper, however, we provide an instance for which BP-MST does not converge. Also, since this instance is small and simple, we believe that BP-MST does not converge for most instances encountered in practice.

MFCS Conference 2013 Conference Paper

Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems

• Karl Bringmann
• Christian Engels
• Bodo Manthey
• B. V. Raghavendra Rao

Abstract Probabilistic analysis for metric optimization problems has mostly been conducted on random Euclidean instances, but little is known about metric instances drawn from distributions other than the Euclidean. This motivates our study of random metric instances for optimization problems obtained as follows: Every edge of a complete graph gets a weight drawn independently at random. The length of an edge is then the length of a shortest path (with respect to the weights drawn) that connects its two endpoints. We prove structural properties of the random shortest path metrics generated in this way. Our main structural contribution is the construction of a good clustering. Then we apply these findings to analyze the approximation ratios of heuristics for matching, the traveling salesman problem (TSP), and the k -center problem, as well as the running-time of the 2-opt heuristic for the TSP. The bounds that we obtain are considerably better than the respective worst-case bounds. This suggests that random shortest path metrics are easy instances, similar to random Euclidean instances, albeit for completely different structural reasons.

SODA Conference 2013 Conference Paper

Smoothed Analysis of the Successive Shortest Path Algorithm

• Tobias Brunsch
• Kamiel Cornelissen
• Bodo Manthey
• Heiko Röglin

MFCS Conference 2012 Conference Paper

Smoothed Complexity Theory

• Markus Bläser
• Bodo Manthey

Abstract Smoothed analysis is a new way of analyzing algorithms introduced by Spielman and Teng ( J. ACM, 2004). Classical methods like worst-case or average-case analysis have accompanying complexity classes, like P and Avg − P, respectively. While worst-case or average-case analysis give us a means to talk about the running time of a particular algorithm, complexity classes allows us to talk about the inherent difficulty of problems. Smoothed analysis is a hybrid of worst-case and average-case analysis and compensates some of their drawbacks. Despite its success for the analysis of single algorithms and problems, there is no embedding of smoothed analysis into computational complexity theory, which is necessary to classify problems according to their intrinsic difficulty. We propose a framework for smoothed complexity theory, define the relevant classes, and prove some first results.

SODA Conference 2009 Conference Paper

Improved smoothed analysis of the k -means method

• Bodo Manthey
• Heiko Röglin

FOCS Conference 2009 Conference Paper

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 worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points. In this paper, we settle the smoothed running time of the k-means method. We show that the smoothed number of iterations is bounded by a polynomial in n and 1/sigma, where sigma is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.

MFCS Conference 2008 Conference Paper

Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise

• Bodo Manthey
• Till Tantau

Abstract Binary search trees are a fundamental data structure and their height plays a key role in the analysis of divide-and-conquer algorithms like quicksort. We analyze their smoothed height under additive uniform noise: An adversary chooses a sequence of n real numbers in the range [0, 1], each number is individually perturbed by adding a value drawn uniformly at random from an interval of size d, and the resulting numbers are inserted into a search tree. An analysis of the smoothed tree height subject to n and d lies at the heart of our paper: We prove that the smoothed height of binary search trees is \(\Theta (\sqrt{n/d} + \log n)\), where d ≥ 1/ n may depend on n. Our analysis starts with the simpler problem of determining the smoothed number of left-to-right maxima in a sequence. We establish matching bounds, namely once more \(\Theta (\sqrt{n/d} + \log n)\). We also apply our findings to the performance of the quicksort algorithm and prove that the smoothed number of comparisons made by quicksort is \(\Theta(\frac{n}{d+1} \sqrt{n/d} + n \log n)\).

TCS Journal 2007 Journal Article

Smoothed analysis of binary search trees

• Bodo Manthey
• Rüdiger Reischuk

Binary search trees are one of the most fundamental data structures. While the height of such a tree may be linear in the worst case, the average height with respect to the uniform distribution is only logarithmic. The exact value is one of the best studied problems in average-case complexity. We investigate what happens in between by analysing the smoothed height of binary search trees: Randomly perturb a given (adversarial) sequence and then take the expected height of the binary search tree generated by the resulting sequence. As perturbation models, we consider partial permutations, partial alterations, and partial deletions. On the one hand, we prove tight lower and upper bounds of roughly Θ ( ( 1 − p ) ⋅ n / p ) for the expected height of binary search trees under partial permutations and partial alterations, where n is the number of elements and p is the smoothing parameter. This means that worst-case instances are rare and disappear under slight perturbations. On the other hand, we examine how much a perturbation can increase the height of a binary search tree, i. e. how much worse well balanced instances can become.

TCS Journal 2005 Journal Article

The intractability of computing the Hamming distance

• Bodo Manthey
• Rüdiger Reischuk

Given a string x and a language L, the Hamming distance of x to L is the minimum Hamming distance of x to any string in L. The edit distance of a string to a language is analogously defined. First, we prove that there is a language in AC 0 such that both Hamming and edit distance to this language are hard to approximate; they cannot be approximated with factor O ( n ( 1 / 3 ) - ε ), for any ε > 0, unless P = NP (n denotes the length of the input string). Second, we show the parameterized intractability of computing the Hamming distance. We prove that for every t ∈ N there exists a language in AC 0 for which computing the Hamming distance is W [ t ] -hard. Moreover, there is a language in P for which computing the Hamming distance is WP -hard. Then we show that the problems of computing the Hamming distance and of computing the edit distance are in some sense equivalent by presenting approximation ratio preserving reductions from the former to the latter and vice versa. Finally, we define HamP to be the class of languages to which the Hamming distance can efficiently, i. e. in polynomial time, be computed. We show some properties of the class HamP. On the other hand, we give evidence that a characterization in terms of automata or formal languages might be difficult.

TCS Journal 2003 Journal Article

Non-approximability of weighted multiple sequence alignment

• Bodo Manthey

We consider a weighted generalization of multiple sequence alignment (MSA) with sum-of-pair score. MSA without weights is known to be NP -complete and can be approximated within a constant factor, but it is unknown whether it has a polynomial time approximation scheme. Weighted multiple sequence alignment (WMSA) can be approximated within a factor of O(log2 n) where n is the number of sequences. We prove that WMSA alignment is MAX SNP -hard and establish a numerical lower bound on its approximability, namely 324 323 −ε. This lower bound is obtained already for the simple binary weighted case where the weights are restricted to 0 and 1. Furthermore, we show that WMSA and its restriction to binary weights can be approximated to the same degree.