Author Publications

2013

Bläser, Markus and Manthey, Bodo and Rao, B.V. Raghavendra (2013) Smoothed analysis of partitioning algorithms for Euclidean functionals. Algorithmica, 66 (2). pp. 397-418. ISSN 0178-4617

Bomhoff, Matthijs and Manthey, Bodo (2013) Bisimplicial edges in bipartite graphs. Discrete applied mathematics, 161 (12). pp. 1699-1706. ISSN 0166-218X

Brunsch, T. and Cornelissen, K. and Manthey, B. and Röglin, H. (2013) Smoothed analysis of the successive shortest path algorithm. In: 24th ACM-SIAM Symposium on Discrete Algorithms 2013, 6-8 January 2013, New Orleans, LA, USA.

Brunsch, Tobias and Cornelissen, Kamiel and Manthey, Bodo and Röglin, Heiko (2013) Smoothed analysis of belief propagation for minimum-cost flow and matching. In: 7th International Workshop on Algorithms and Computation, WALCOM 2013, 14-16 February 2013, Kharagpur, India.

Manthey, Bodo and Plociennik, Kai (2013) Approximating independent set in perturbed graphs. Discrete applied mathematics, 161 (12). pp. 1761-1768. ISSN 0166-218X

2012

Bläser, Markus and Manthey, Bodo (2012) Smoothed complexity theory. In: 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012, 27-31 August 2012, Bratislava, Slovakia.

Damerow, Valentina and Manthey, Bodo and Meyer auf der Heide, Friedhelm and Räcke, Heide Harald and Scheideler, Christian and Sohler, Christian and Tantau, Till (2012) Smoothed analysis of left-to-right maxima with applications. ACM Transactions on Algorithms, 8 (3). p. 30. ISSN 1549-6325

Engels, Christian and Manthey, Bodo and Raghavendra Rao, B.V. (2012) Random shortest path metrics with applications. In: Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012), 29-31 May 2012, Munich, Germany.

Fouz, Mahmoud and Kufleitner, Manfred and Manthey, Bodo and Zeini Jahromi, Nima (2012) On smoothed analysis of quicksort and Hoare's find. Algorithmica, 62 (3-4). pp. 879-905. ISSN 0178-4617

Manthey, Bodo (2012) Multi-criteria TSP: Min and max combined. Operations Research Letters, 40 (1). pp. 36-38. ISSN 0167-6377

Manthey, Bodo (2012) On approximating multi-criteria TSP. ACM Transactions on Algorithms, 8 (2). p. 17. ISSN 1549-6325

Manthey, Bodo (2012) Deterministic algorithms for multi-criteria Max-TSP. Discrete Applied Mathematics, 160 (15). pp. 2277-2285. ISSN 0166-218X

2011

Arthur, David and Manthey, Bodo and Röglin, Heiko (2011) Smoothed analysis of the k-means method. Journal of the ACM, 58 (5). p. 19. ISSN 0004-5411

Bläser, Markus and Jakoby, Andreas and Liskiewicz, Maciej and Manthey, Bodo (2011) Privacy in non-private environments. Theory of Computing Systems, 48 (1). pp. 211-245. ISSN 1432-4350

Bläser, Markus and Manthey, Bodo and Rao, B.V. Raghavendra (2011) Smoothed analysis of partitioning algorithms for Euclidean functionals. In: 12th International Symposium on Algorithms and Data Structures, WADS 2011, 15-17 Aug 2011, New York, NY, USA.

Boros, Endre and Elbassioni, Khaled and Fouz, Mahmoud and Gurvich, Vladimir and Makino, Kazuhisa and Manthey, Bodo (2011) Stochastic mean payoff games: smoothed analysis and approximation schemes. In: 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, 4-8 July 2011, Zurich, Switzerland.

Manthey, Bodo (2011) Deterministic algorithms for multi-criteria TSP. In: 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011, 23-25 May 2011, Tokyo, Japan.

Manthey, Bodo (2011) Towards explaining the speed of -means. Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica, 2011 . pp. 45-54.

Manthey, Bodo and Röglin, Heiko (2011) Smoothed analysis: analysis of algorithms beyond worst case. it - Information Technology, 53 (6). pp. 280-286. ISSN 1611-2776

2010

Bomhoff, Matthijs and Manthey, Bodo (2010) Bisimplicial edges in bipartite graphs. In: Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010, 25-27 May 2010, Cologne, Germany.

Manthey, Bodo (2010) Multi-criteria TSP: Min and Max combined. In: 7th International Workshop Approximation and Online Algorithms, WAOA 2009, 10-11 September 2009, Copenhagen, Denmark.

Manthey, Bodo and Plociennik, Kai (2010) Approximating independent set in semi-random graphs. In: 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010, 25-27 May 2010, Cologne, Germany.

2009

Arpe, J. and Manthey, B. (2009) Approximability of Minimum AND-Circuits. Algorithmica, 53 (3). pp. 337-357. ISSN 0178-4617

Arthur, David and Manthey, Bodo and Röglin, Heiko (2009) k-Means has polynomial smoothed complexity. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, 24-27 Oct 2009, Atlanta, GA, USA.

Engels, Christian and Manthey, Bodo (2009) Average-case approximation ratio of the 2-opt algorithm for the TSP. Operations Research Letters, 37 (2). pp. 83-84. ISSN 0167-6377

Fouz, Mahmoud and Kufleitner, Manfred and Manthey, Bodo and Zeini Jahromi, Nima (2009) On smoothed analysis of quicksort and Hoare's find. In: 15th Annual International Computing and Combinatorics Conference, COCOON 2009, 13-15 Jul 2009, Niagara Falls, NY, USA.

Manthey, B. (2009) Minimum-weight cycle covers and their approximability. Discrete Applied Mathematics, 157 (7). pp. 1470-1480. ISSN 0166-218X

Manthey, B. and Shankar Ram, L. (2009) Approximation algorithms for multi-criteria traveling salesman problems. Algorithmica, 53 (1). pp. 69-88. ISSN 0178-4617

Manthey, Bodo (2009) On approximating multi-criteria TSP. In: 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, 26-28 Feb 2009, Freiburg, Germany.

Manthey, Bodo and Röglin, Heiko (2009) Worst-case and smoothed analysis of -means clustering with Bregman divergences. In: 20th International Symposium on Algorithms and Computation, ISAAC 2009, 16-18 Dec 2009, Honolulu, Hawaii, USA.

Manthey, Bodo and Röglin, Heiko (2009) Improved smoothed analysis of the -means method. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, 4-6 Jan 2009, New York, NY, USA.

2008

Bläser, Markus and Heynen, Thomas and Manthey, Bodo (2008) Adding cardinality constraints to integer programs with applications to maximum satisfiability. Information Processing Letters, 105 (5). pp. 194-198. ISSN 0020-0190

Manthey, Bodo (2008) On approximating restricted cycle covers. SIAM Journal on Computing, 38 (1). pp. 181-206. ISSN 0097-5397

2007

Manthey, Bodo and Reischuk, Rüdiger (2007) Smoothed analysis of binary search trees. Theoretical Computer Science, 378 (3). pp. 292-315. ISSN 0304-3975

2006

Bläser, Markus and Jakoby, Andreas and Liśkiewicz, Maciej and Manthey, Bodo (2006) Private computation: k-connected versus 1-connected networks. Journal of Cryptology, 19 (3). pp. 341-357. ISSN 0933-2790

Bläser, Markus and Manthey, Bodo and Sgall, Jirí (2006) An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. Journal of Discrete Algorithms, 4 (4). pp. 623-632. ISSN 1468-0904

2005

Bläser, Markus and Manthey, Bodo (2005) Approximating maximum weight cycle covers in directed graphs with weights zero and one. Algorithmica, 42 (2). pp. 121-139. ISSN 0178-4617

Manthey, Bodo (2005) Non-approximability of weighted multiple sequence alignment for arbitrary metrics. Information Processing Letters, 95 (3). pp. 389-395. ISSN 0020-0190

Manthey, Bodo and Reischuk, Rüdiger (2005) The intractability of computing the Hamming distance. Theoretical Computer Science, 337 (1-3). pp. 331-346. ISSN 0304-3975

2004

Liśkiewicz, Maciej and Manthey, Bodo (2004) New lower and upper bounds for the competitive ratio of transmission protocols. Information Processing Letters, 89 (6). pp. 297-301. ISSN 0020-0190

2003

Böhme, Martin and Manthey, Bodo (2003) The computational power of compiling C++. Bulletin of the European Association for Theoretical Computer Science, 81 . pp. 264-270. ISSN 0252-9742

Manthey, Bodo (2003) Non-approximability of weighted multiple sequence alignment. Theoretical Computer Science, 296 (1). pp. 179-192. ISSN 0304-3975