Bodo Manthey – Publications

Journal Articles

[J23]	Bodo Manthey. On Approximating Multi-Criteria TSP. ACM Transactions on Algorithms, to appear.
[J22]	Valentina Damerow, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, Till Tantau. Smoothed Analysis of Left-To-Right Maxima with Applications. ACM Transactions on Algorithms, to appear.
[J21]	Matthijs Bomhoff, Bodo Manthey. Bisimplicial Edges in Bipartite Graphs. Discrete Applied Mathematics, to appear.
[J20]	Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi. On Smoothed Analysis of Quicksort and Hoare's Find. Algorithmica, 62(3-4):879-905, 2012.
[J19]	Bodo Manthey. Multi-Criteria TSP: Min and Max Combined. Operations Research Letters, 40(1):36-38, 2012.
[J18]	Bodo Manthey, Heiko Röglin. Smoothed Analysis: Analysis of Algorithms Beyond Worst Case. it - Information Technology, 53(6):280-286, 2011.
[J17]	David Arthur, Bodo Manthey, Heiko Röglin. Smoothed Analysis of the k-Means Method. Journal of the ACM, 58(5):19, 2011.
[J16]	Markus Bläser, Andreas Jakoby, Maciej Liśkiewicz, Bodo Manthey. Privacy in Non-Private Environments. Theory of Computing Systems, 48(1):211-245, 2011.
[J15]	Bodo Manthey. Minimum-weight Cycle Covers and Their Approximability. Discrete Applied Mathematics, 157(7), 1470-1480, 2009.
[J14]	Christian Engels, Bodo Manthey. Average-Case Approximation Ratio of the 2-Opt Algorithm for the TSP. Operations Research Letters, 37(2):83-84, 2009.
[J13]	Jan Arpe, Bodo Manthey. Approximability of Minimum AND-Circuits. Algorithmica, 53(3):337-357, 2009.
[J12]	Bodo Manthey, L. Shankar Ram. Approximation Algorithms for Multi-Criteria Traveling Salesman Problems. Algorithmica, 53(1):69-88, 2009.
[J11]	Bodo Manthey. On Approximating Restricted Cycle Covers. SIAM Journal on Computing, 38(1):181-206, 2008.
[J10]	Markus Bläser, Thomas Heynen, Bodo Manthey. Adding Cardinality Constraints to Integer Programs with Applications to Maximum Satisfiability. Information Processing Letters, 105(5):194-198, 2008.
[J9]	Bodo Manthey, Rüdiger Reischuk. Smoothed Analysis of Binary Search Trees. Theoretical Computer Science, 378(3):292-315, 2007.
[J8]	Markus Bläser, Bodo Manthey, Jiří Sgall. An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality. Journal of Discrete Algorithms, 4(4):623-632, 2006.
[J7]	Markus Bläser, Andreas Jakoby, Maciej Liśkiewicz, Bodo Manthey. Private Computation: k-Connected versus 1-Connected Networks. Journal of Cryptology, 19(3):341-357, 2006.
[J6]	Bodo Manthey. Non-approximability of Weighted Multiple Sequence Alignment for Arbitrary Metrics. Information Processing Letters, 95(3):389-395, 2005.
[J5]	Bodo Manthey, Rüdiger Reischuk. The Intractability of Computing the Hamming Distance. Theoretical Computer Science, 337(1-3):331-346, 2005.
[J4]	Markus Bläser, Bodo Manthey. Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One. Algorithmica, 42(2):121-139, 2005.
[J3]	Maciej Liśkiewicz, Bodo Manthey. New Lower and Upper Bounds for the Competitive Ratio of Transmission Protocols. Information Processing Letters, 89(6):297-301, 2004.
[J2]	Martin Böhme, Bodo Manthey. The Computational Power of Compiling C++. Bulletin of the European Association for Theoretical Computer Science, 81:264-270, 2003.
[J1]	Bodo Manthey. Non-approximability of Weighted Multiple Sequence Alignment. Theoretical Computer Science, 296(1):179-192, 2003.

Conference Papers

[C25]	Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao. Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. In Frank Dehne, John Iacono, Jörg-Rüdiger Sack (eds.): Algorithms and Data Structures, 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011, Proceedings, vol. 6844 of Lecture Notes in Computer Science, pp. 110-121. Springer, 2011. Full paper.
[C24]	Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey. Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes. In Luca Aceto, Monika Henzinger, Jiří Sgall (eds.): Automata, Languages and Programming, 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, vol. 6755 of Lecture Notes in Computer Science, pp. 147-158. Springer, 2011. Full paper.
[C23]	Bodo Manthey. Deterministic Algorithms for Multi-Criteria TSP. In Mitsuniro Ogihara, Jun Tarui (eds.): Theory and Applications of Models of Computation, 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011, Proceedings, vol. 6648 of Lecture Notes in Computer Science, pp. 264-275. Springer, 2011. Full paper.
[C22]	Bodo Manthey. Multi-Criteria TSP: Min and Max Combined. In Evripidis Bampis, Klaus Jansen (eds.): Approximation and Online Algorithms, 7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Papers, vol. 5893 of Lecture Notes in Computer Science, pp. 205-216. Springer, 2010. Superseded by journal article [J19].
[C21]	Bodo Manthey, Heiko Röglin. Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences. In Yingfei Dong, Ding-Zhu Du, Oscar Ibarra (eds.): Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009, Proceedings, vol. 5878 of Lecture Notes in Computer Science, pp. 1024-1033. Springer, 2009. Full paper.
[C20]	David Arthur, Bodo Manthey, Heiko Röglin. k-Means has Polynomial Smoothed Complexity. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), October 24-27, 2009, Atlanta, GA, USA, pp. 405-414. IEEE Computer Society, 2009. Superseded by journal article [J17].
[C19]	Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi. On Smoothed Analysis of Quicksort and Hoare's Find. In Hung Q. Ngo (ed.): Computing and Combinatorics, 15th Annual International Conference, COCOON 2009, Niagara Falls, NY, USA, July 2009, Proceedings, vol. 5609 of Lecture Notes in Computer Science, pp. 158-167. Springer, 2009. Superseded by journal article [J20].
[C18]	Bodo Manthey. On Approximating Multi-Criteria TSP. In Susanne Albers, Jean-Yves Marion (eds.): Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp. 637-648. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2009. Superseded by journal article [J23].
[C17]	Bodo Manthey, Heiko Röglin. Improved Smoothed Analysis of the k-Means Method. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pp. 461-470. SIAM, 2009. Superseded by journal article [J17] and the full version of conference paper [C21].
[C16]	Markus Bläser, Bodo Manthey, Oliver Putz. Approximating Multi-Criteria Max-TSP. In Dan Halperin, Kurt Mehlhorn (eds.): Algorithms – ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings, vol. 5193 of Lecture Notes in Computer Science, pp. 185-197. Springer, 2008. Full paper: arXiv:0806.3668 [cs.DS], 2008.
[C15]	Bodo Manthey, Till Tantau. Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. In Edward Ochmański, Jerzy Tyszkiewicz (eds.): Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Toruń, Poland, August 25-29, 2008, Proceedings, vol. 5162 of Lecture Notes in Computer Science, pp. 467-478. Springer, 2008. Superseded by journal article [J22].
[C14]	Bodo Manthey. Minimum-weight Cycle Covers and Their Approximability. In Andreas Brandstädt, Dieter Kratsch, Haiko Müller (eds.): Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers, vol. 4769 of Lecture Notes in Computer Science, pp. 178-189. Springer, 2007. Superseded by journal article [J15].
[C13]	Bodo Manthey, L. Shankar Ram. Approximation Algorithms for Multi-criteria Traveling Salesman Problems. In Thomas Erlebach, Christos Kaklamanis (eds.): Approximation and Online Algorithms, Fourth International Workshop, WAOA 2006, Zurich, Switzerland, September 14-15, 2006, Revised Papers, vol. 4368 of Lecture Notes in Computer Science, pp. 302-315. Springer, 2007. Superseded by journal article [J12].
[C12]	Bodo Manthey. Approximations Algorithms for Restricted Cycle Covers Based on Cycle Decompositions. In Fedor V. Fomin (ed.): Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers, vol. 4271 of Lecture Notes in Computer Science, pp. 336-347. Springer, 2006. Superseded by journal article [J11].
[C11]	Jan Arpe, Bodo Manthey. Approximability of Minimum AND-Circuits. In Lars Arge, Rusins Freivalds (eds.): Algorithm Theory – SWAT 2006, 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings, vol. 4059 of Lecture Notes in Computer Science, pp. 292-303. Springer, 2006. Superseded by journal article [J13].
[C10]	Bodo Manthey. On Approximating Restricted Cycle Covers. In Thomas Erlebach, Giuseppe Persiano (eds.): Approximation and Online Algorithms, Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers, vol. 3879 of Lecture Notes in Computer Science, pp. 282-295. Springer, 2006. Superseded by journal article [J11].
[C9]	Bodo Manthey, Rüdiger Reischuk. Smoothed Analysis of Binary Search Trees. In Xiaotie Deng, Dingzhu Du (eds.): Algorithms and Computation, 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, vol. 3827 of Lecture Notes in Computer Science, pp. 483-492. Springer, 2005. Invited to a special issue of Theoretical Computer Science [J9].
[C8]	Markus Bläser, Andreas Jakoby, Maciej Liśkiewicz, Bodo Manthey. Privacy in Non-private Environments. In Pil Joong Lee (ed.): Advances in Cryptology – ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings, vol. 3329 of Lecture Notes in Computer Science, pp. 137-151. Springer, 2004. Superseded by journal article [J16].
[C7]	Bodo Manthey, Rüdiger Reischuk. The Intractability of Computing the Hamming Distance. In Toshihide Ibaraki, Naoki Katoh, Hirotaka Ono (eds.): Algorithms and Computation, 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 2003, Proceedings, vol. 2906 of Lectures Notes in Computer Science, pp. 88-97. Springer, 2003. Superseded by journal article [J5].
[C6]	Markus Bläser, Bodo Manthey. Budget Balanced Mechanisms for the Multicast Pricing Problem with Rates. In: Proceedings of the 4th ACM Conference on Electronic Commerce (EC 2003), San Diego, California, USA, June 9-12, 2003, pp. 194-195. ACM, 2003.
[C5]	Markus Bläser, Bodo Manthey. Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint. In Prosenjit Bose, Pat Morin (eds.): Algorithms and Computation, 13th International Symposium, ISAAC 2002, Vancouver, BC, Canada, November 2002, Proceedings, vol. 2518 of Lectures Notes in Computer Science, pp. 187-198. Springer, 2002. Partially superseded by journal article [J10].
[C4]	Markus Bläser, Bodo Manthey. Two Approximation Algorithms for 3-Cycle Covers. In Klaus Jansen, Stefano Leonardi, Vijay Vazirani (eds.): Approximation Algorithms for Combinatorial Optimization, 5th International Workshop, APPROX 2002, Rome, Italy, September 2002, Proceedings, vol. 2462 of Lecture Notes in Computer Science, pp. 40-50. Springer, 2002. Partially superseded by journal article [J4].
[C3]	Markus Bläser, Andreas Jakoby, Maciej Liśkiewicz, Bodo Siebert. Private Computation – k-Connected versus 1-Connected Networks. In Moti Yung (ed.): Advances in Cryptology – CRYPTO 2002, 22nd Annual International Conference, Santa Barbara, California, USA, August 2002, Proceedings, vol. 2442 of Lecture Notes in Computer Science, pp. 194-209. IACR, Springer, 2002. Superseded by journal article [J7]. Bodo Siebert is Bodo Manthey's birth name.
[C2]	Markus Bläser, Bodo Siebert. Computing Cycle Covers without Short Cycles. In Friedhelm Meyer auf der Heide (ed.): Algorithms – ESA 2001, 9th Annual European Symposium, Århus, Denmark, August 2001, Proceedings, vol. 2161 of Lecture Notes in Computer Science, pp. 368-379. Springer, 2001. Partially superseded by journal article [J4]. Bodo Siebert is Bodo Manthey's birth name.
[C1]	Bodo Siebert. Non-approximability of Weighted Multiple Sequence Alignment. In Jie Wang (ed.): Computing and Combinatorics, 7th Annual International Conference, COCOON 2001, Guilin, China, August 2001, Proceedings, vol. 2108 of Lecture Notes in Computer Science, pp. 75-85. Springer, 2001. Invited to a special issue of Theoretical Computer Science [J1]. Bodo Siebert is Bodo Manthey's birth name.

Other Publications

[O9]	Markus Bläser, Bodo Manthey. Smoothed Complexity Theory. Computing Research Repository, arXiv:1202.1936v1 [cs.CC], 2012.
[O8]	Bodo Manthey. Towards Explaining the Speed of k-Means Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica (NVTI), 15:45-54, 2011.
[O7]	Bodo Manthey. Approximability of Cycle Covers and Smoothed Analysis of Binary Search Trees. In Dorothea Wagner, Abraham Bernstein, Thomas Dreier, Steffen Hölldobler, Günter Hotz, Klaus-Peter Löhr, Paul Molitor, Gustaf Neumann, Rüdiger Reischuk, Dietmar Saupe, and Myra Spiliopoulou (eds.): Ausgezeichnete Informatikdissertationen 2005, vol. D-6 of GI-Edition – Lecture Notes in Informatics, pp. 57-66. Köllen, 2006.
[O6]	Bodo Manthey. Approximability of Cycle Covers and Smoothed Analysis of Binary Search Trees. Dissertation (Doctoral Thesis), Universität zu Lübeck, Technisch-Naturwissenschaftliche Fakultät, Institut für Theoretische Informatik, December 2005.
[O5]	Jan Arpe, Bodo Manthey, Rüdiger Reischuk (eds.). 52. Workshop über Komplexitätstheorie, Datenstrukturen und Effiziente Algorithmen ("Theorietag"). Schriftenreihe der Institute für Informatik und Mathematik, Technical Report B-05-04, University of Lübeck, 2006.
[O4]	Bodo Manthey, Jan Arpe, Andreas Jakoby, Rüdiger Reischuk. Institut für Theoretische Informatik: Theoretische Informatik und das Problem des Handlungsreisenden. FOCUS MUL, 21(3/4):195-198, 2004.
[O3]	Martin Böhme, Rainer Hagenau, Jan Modersitzki, Bodo Siebert. Non-Linear Image Registration on PC-Clusters Using Parallel FFT Techniques. Schriftenreihe der Institute für Informatik und Mathematik, Technical Report A-02-08, University of Lübeck, 2002. Bodo Siebert is Bodo Manthey's birth name.
[O2]	Bodo Siebert. Eine untere Schranke für die Approximierbarkeit des gewichteten Multiple-Sequence-Alignment-Problems. Diplomarbeit (Diploma Thesis), Medizinische Universität zu Lübeck, Institut für Theoretische Informatik, September 2000. Bodo Siebert is Bodo Manthey's birth name.
[O1]	Bodo Siebert. Die Komplexität des Multiple Sequence Alignment Problems bei nichtmetrischen Kostenfunktionen. Studienarbeit (Student's Thesis), Medizinische Universität zu Lübeck, Institut für Theoretische Informatik, 2000. Bodo Siebert is Bodo Manthey's birth name.