On Smoothed Analysis of Quicksort and Hoare's Find (2009)
Fouz, Mahmoud, Kufleitner, Manfred, Manthey, Bodo, Jahromi, Nima Zeini
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-implement algorithm for...
k-Means has Polynomial Smoothed Complexity (2009)
Arthur, David, Manthey, Bodo, Röglin, Heiko
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...
On Smoothed Analysis of Quicksort and Hoare's Find (2009)
Fouz, Mahmoud, Kufleitner, Manfred, Manthey, Bodo, Zeini Jahromi, Nima
21 pages
On Approximating Multi-Criteria TSP (2009)
We present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP), whose performances are independent of the number $k$ of criteria and come close to...
On Approximating Multi-Criteria TSP (2009)
We present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP), whose performances are independent of the number $k$ of criteria and come close to...
On Smoothed Analysis of Quicksort and Hoare's Find (2009)
Fouz, Mahmoud, Kufleitner, Manfred, Manthey, Bodo, Zeini Jahromi, Nima
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-implement algorithm for...
On Approximating Multi-Criteria TSP (2009)
We present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP), whose performances are independent of the number $k$ of criteria and come close to...
Improved Smoothed Analysis of the k-Means Method (2008)
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 a gap between...
Approximating Multi-Criteria Max-TSP (2008)
Bläser, Markus, Manthey, Bodo, Putz, Oliver
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 arbitrarily small $\eps >...
Approximability of Cycle Covers and Smoothed Analysis of Binary Search Trees (2008)
Bodo Manthey, Zur Erlangung Der, Bodo Manthey, Berichterstatter Prof, Dr. Rüdiger Reischuk, ...
the years. I also thank the current and former members of the Institut für Theoretische Informatik at the Universität zu Lübeck for many valuable discussions, not only about computer science. In...
Approximability of Minimum AND-Circuits ⋆ Jan Arpe1,⋆ ⋆ 2, ⋆ ⋆ ⋆ (2008)
Abstract. Given a set of monomials, the Minimum-AND-Circuit problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. We prove that the problem...
New lower and upper bounds for the competitive ratio of transmission protocols (2008)
Transmission protocols like TCP are usually divided into a time scheduling and a data selection policy. We consider on-line algorithms of data selection policies for any time scheduling policy and...
Minimum-weight Cycle Covers and Their Approximability ⋆ (2008)
Abstract. 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 L ⊆ N....
Approximability of Minimum AND-Circuits ∗ (2008)
Given a set of monomials, the Minimum AND-Circuit problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. We prove that the problem is not...
Abstract The Intractability of Computing the Hamming Distance ⋆ (2008)
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,...
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise (2008)
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. Their worst-case height is linear;...
The Intractability of Computing the Hamming Distance (2008)
Bodo Manthey, Rüdiger Reischuk
Abstract. 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...
The Intractability of Computing the Hamming Distance (2007)
Rüdiger Reischuk, Serie A, Technisch-naturwissenschaftliche Fakultat, Bodo Manthey, Bodo Manthey, Rudiger Reischuk
Given a language L, the Hamming distance of a string x to L is the minimum Hamming distance of x to any string in L. The edit distance of a string to a given language is defined similarly.
On Approximating Multi-Criteria TSP (2007)
We present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP), whose performances are independent of the number k of criteria and come close to...
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. Their worst-case height is linear; their...
Approximation algorithms for multi-criteria traveling salesman problems (2007)
Bodo Manthey, L. Shankar Ram, Eth Zürich
We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with γ-triangle inequality....
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise (2007)
While the height of binary search trees is linear in the worst case, their average height is logarithmic. We investigate what happens in between, i.e., when the randomness is limited, by analyzing...
Minimum-weight Cycle Covers and Their Approximability (2006)
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 L. We investigate...
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems (2006)
Manthey, Bodo, Ram, L. Shankar
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 cannot consider only...
Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions (2006)
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 L. The weight of a...
aus der Technisch-Naturwissenschaftlichen Fakultät (2006)
Jan Arpe, Jan Arpe, Berichterstatter Prof, Dr. Rüdiger Reischuk, Prof Dr, ...
In the first place, I would like to thank my Doktorvater Rüdiger Reischuk for giving me the opportunity to work and to carry out my research at the Institut für Theoretische Informatik of the...
Approximability of minimum AND-circuits (2006)
Given a set of monomials, the Minimum AND-Circuit problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. We prove that the problem is not...
Approximability of Minimum AND-Circuits (2006)
Given a set of monomials, the {sc Minimum AND-Circuit} problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. We prove that the problem is...
On Approximating Restricted Cycle Covers (2005)
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 L. The weight of a...
Smoothed analysis of binary search trees (2005)
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...
Jan Arpe, Bodo Manthey, Rüdiger Reischuk, Serie B, ...
Gesellschaft für Informatik (GI) veranstaltet. Er ermöglicht einen intensiven Dialog
R.: Smoothed analysis of binary search trees (2005)
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...
On approximating restricted cycle covers (2005)
Abstract. 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 L. A...
Approximating maximum weight cycle covers in directed graphs with weights zero and one (2005)
A cycle cover of a graph is a spanning subgraph each node of which is part of exactly one simple cycle. A k-cycle cover is a cycle cover where each cycle has length at least k. Given a complete...
Markus Bläser, Bodo Manthey, Jiri Sgall
We consider the asymmetric traveling salesperson problem with γ-parameterized triangle inequality for γ ∈ [½, 1). That means, the edge weights fulfill w(u, v)...
Markus Blaser, Bodo Manthey, Jir Sgall
We consider the asymmetric traveling salesperson problem with #-parameterized triangle inequality for #
The computational power of compiling C (2003)
Using a C++ compiler, any partial recursive function can be computed at compile time. We show this by using the C++ template mechanism to define functions via primitive recursion, composition, and...
Budget Balanced Mechanisms for the Multicast Pricing Problem with Rates (2003)
Markus Bläser, Markus Bl Aser, Bodo Manthey
Multicast transmissions allow huge savings of network traffic compared to unicast transmissions when the same data is sent to a lot of users. These savings are achieved by the fact that users may...
A new approximation algorithm for the asymmetric TSP with triangle inequality (2003)
Abstract We consider the asymmetric traveling salesperson problem with fl-parameterized tri-angle inequality for
The computational power of compiling C (2003)
Using a C++ compiler, any partial recursive function can be computed at compile time. We show this by using the C++ template mechanism to define functions via primitive recursion, composition, and...
Non-approximability of weighted multiple sequence alignment (2003)
We prove that the multiple sequence alignment problem with weighted sum-of-pairs score is APX-hard for arbitrary metric scoring functions over the binary alphabet. This holds even when the weights...
Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint (2002)
Max-2SAT-CC is the Max-2SAT problem with the additional cardinality constraint that the value one may be assigned to at most K variables. For any ffl ? 0, we obtain a 16+2\Deltae \Gamma ffl 0:6603...
Private computation — k-connected versus 1-connected networks (2002)
Markus Bläser, Andreas Jakoby, Bodo Manthey
We study the role of connectivity of communication networks in private computations under information theoretic settings. We show that some functions can be computed by private protocols even if the...
Two approximation algorithms for 3-cycle covers (2002)
A cycle cover of a directed graph is a collection of node disjoint cycles such that every node is part of exactly one cycle. A k-cycle cover is a cycle cover in which every cycle has length at least...