385 citations
- Institute for Solid State Physics and OpticsHU2 papers
- Institut Laue-LangevinFR2 papers
- Johannes Gutenberg University MainzDE2 papers
- Karlsruhe Institute of TechnologyDE2 papers
- Max Planck Institute for Chemical Physics of SolidsDE2 papers
- Max Planck Institute for InformaticsDE2 papers
- Max Planck SocietyDE2 papers
- University of BayreuthDE2 papers
- University of BonnDE2 papers
- University of California, BerkeleyUS2 papers
- Balseiro InstituteAR1 paper
- Bariloche Atomic CentreAR1 paper
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2009
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…
cs.DS2008★ 3 cited
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…
cs.DS2006
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…