Follow
Bodo Manthey
Title
Cited by
Cited by
Year
Smoothed analysis of the k-means method
D Arthur, B Manthey, H Röglin
Journal of the ACM (JACM) 58 (5), 1-31, 2011
1362011
k-Means has Polynomial Smoothed Complexity
D Arthur, B Manthey, H Röglin
Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium …, 2009
742009
Average-case approximation ratio of the 2-opt algorithm for the TSP
C Engels, B Manthey
Operations Research Letters 37 (2), 83-84, 2009
472009
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
M Bläser, B Manthey, J Sgall
Journal of discrete algorithms 4 (4), 623-632, 2006
452006
Smoothed analysis of binary search trees
B Manthey, R Reischuk
Theoretical Computer Science 378 (3), 292-315, 2007
412007
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences
B Manthey, H Röglin
International Symposium on Algorithms and Computation, 1024-1033, 2009
38*2009
Improved Smoothed Analysis of the k-Means Method
B Manthey, H Röglin
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete …, 2009
382009
Computing cycle covers without short cycles
M Bläser, B Siebert
Algorithms—ESA 2001, 368-379, 2001
382001
Smoothed analysis of the successive shortest path algorithm
T Brunsch, K Cornelissen, B Manthey, H Röglin, C Rösner
SIAM Journal on Computing 44 (6), 1798-1819, 2015
362015
Approximating maximum weight cycle covers in directed graphs with weights zero and one
M Bläser, B Manthey
Algorithmica 42, 121-139, 2005
352005
Approximation algorithms for multi-criteria traveling salesman problems
B Manthey, L Shankar Ram
Algorithmica 53 (1), 69-88, 2009
302009
On approximating restricted cycle covers
B Manthey
SIAM Journal on Computing 38 (1), 181-206, 2008
302008
Private computation: k-connected versus 1-connected networks
M Bläser, A Jakoby, M Liskiewicz, B Manthey
Journal of cryptology 19 (3), 341-357, 2006
29*2006
Smoothed analysis: analysis of algorithms beyond worst case
B Manthey, H Röglin
IT-Information Technology 53 (6), 280-286, 2011
282011
Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions
E Boros, K Elbassioni, M Fouz, V Gurvich, K Makino, B Manthey
Algorithmica 80, 3132-3157, 2018
27*2018
Smoothed analysis of the 2-Opt heuristic for the TSP: Polynomial bounds for Gaussian noise
B Manthey, R Veenstra
Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong …, 2013
272013
On approximating multicriteria TSP
B Manthey
ACM Transactions on Algorithms (TALG) 8 (2), 1-18, 2012
252012
Smoothed analysis of belief propagation for minimum-cost flow and matching
T Brunsch, K Cornelissen, B Manthey, H Röglin
International Workshop on Algorithms and Computation, 182-193, 2013
222013
Minimum-weight cycle covers and their approximability
B Manthey
Discrete Applied Mathematics 157 (7), 1470-1480, 2009
212009
Smoothed analysis of partitioning algorithms for Euclidean functionals
M Bläser, B Manthey, BVR Rao
Algorithmica 66, 397-418, 2013
192013
The system can't perform the operation now. Try again later.
Articles 1–20