Bodo Manthey

Bodo Manthey
	Faculty of Electrical Engineering, Mathematics and Computer Science
	Discrete Mathematics and Mathematical Programming

Position:	Associate Professor
Address:	University of Twente Department of Applied Mathematics P. O. Box 217 7500 AE Enschede The Netherlands
Office:	Building Zilverling Room 4010
Phone:	+31 53 489 3385
Email:	"b.manthey" at "utwente.nl"

Short CV
since 2015	associate professor at the University of Twente
2009-2015	assistant professor at the University of Twente
2006-2009	postdoc at Saarland University
2006-2007	postdoc at Yale University
2001-2006	PhD candidate and postdoc at University of Lübeck
1996-2000	student of computer science at University of Lübeck

2012	habilitation for computer science, Saarland University
2005	PhD (Dr. rer. nat.) in computer science, University of Lübeck
2000	diploma in computer science (roughly equivalent to MSc.), University of Lübeck

Teaching (only national courses)

Spring 2018: Algorithms Beyond the Worst Case

Fall 2016: Discrete Optimization

Spring 2016: Algorithms Beyond the Worst Case

Fall 2014: Discrete Optimization

Publications
Journal Articles
[J39]	Bodo Manthey, Victor Reijnders. Probabilistic properties of highly connected random geometric graphs. Discrete Applied Mathematics, to appear.
[J38]	Kamiel Cornelissen, Bodo Manthey. Belief Propagation for Maximum-Weight Independent Set and Minimum Spanning Tree Problems. Theoretical Computer Science, 738:53-64, 2018.
[J37]	Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey. Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and a Few Random Positions. Algorithmica, 80(11):3132-3157, 2018.
[J36]	Bodo Manthey, Matthijs Tijink. Perturbation Resilience for the Facility Location Problem. Operations Research Letters, 46(2):215-218, 2018.
[J35]	Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul, Marten Waanders. Approximation Algorithms for Connected Graph Factors of Minimum Weight. Theory of Computing Systems, 62(2):441-464, 2018.
[J34]	Walter Kern, Bodo Manthey. Approximating Bounded-Degree Spanning Trees and Connected Factors with Leaves. Operations Research Letters, 45(2):115-118, 2017.
[J33]	Maurits de Graaf, Bodo Manthey. Probabilistic Analysis of Power Assignments. Random Structures & Algorithms, 51(3), 483-505, 2017.
[J32]	Ruben Hoeksma, Bodo Manthey, Marc Uetz. Efficient Implementation of Caratheodory's Theorem for the Single Machine Scheduling Polytope. Discrete Applied Mathematics, 215:136-145, 2016.
[J31]	Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin, Clemens Rösner. Smoothed Analysis of the Successive Shortest Path Algorithm. SIAM Journal on Computing, 44(6):1798-1819, 2015.
[J30]	Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao. Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems. Algorithmica, 73(1):42-62, 2015.
[J29]	Markus Bläser, Bodo Manthey. Smoothed Complexity Theory. ACM Transactions on Computation Theory, 7(2):6, 2015.
[J28]	Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin. Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching. Journal of Graph Algorithms and Applications, 17(6):647-670, 2013.
[J27]	Bodo Manthey, Heiko Röglin. Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences. Journal of Computational Geometry, 4(1):94-132, 2013.
[J26]	Bodo Manthey, Kai Plociennik. Approximating Independent Set in Perturbed Graphs. Discrete Applied Mathematics, 161(12):1761-1768, 2013.
[J25]	Matthijs Bomhoff, Bodo Manthey. Bisimplicial Edges in Bipartite Graphs. Discrete Applied Mathematics, 161(12):1699-1706, 2013.
[J24]	Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao. Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. Algorithmica, 66(2):397-418, 2013.
[J23]	Bodo Manthey. Deterministic Algorithms for Multi-Criteria TSP. Discrete Applied Mathematics, 160(15):2277-2285, 2012.
[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, 8(3):30, 2012.
[J21]	Bodo Manthey. On Approximating Multi-Criteria TSP. ACM Transactions on Algorithms, 8(2):17, 2012.
[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. Approximabilit 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
[C38]	Stefan Klootwijk, Bodo Manthey, Sander Visser. Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics. Proc. 13th International Conference and Workshops on Algorithms and Computation (WALCOM 2019), to appear.
[C37]	Bodo Manthey, Victor M. J. J. Reijnders. Probabilistic Properties of Highly Connected Random Geometric Graphs. Proc. 4th Annual International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2018), to appear. Invited to a special issue of Discrete Applied Mathematics [J39].
[C36]	Bodo Manthey, Marten Waanders. Approximation Algorithms for k-Connected Graph Factors. Proc. 13th Workshop on Approximation and Online Algorithms (WAOA 2015), vol. 9499 of Lecture Notes in Computer Science, pp. 1-12. Springer, 2016. Invited to a special issue of Theory of Computing Systems [J35].
[C35]	Kamiel Cornelissen, Bodo Manthey. Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. Proc. 21st Int. Computing and Combinatorics Conference (COCOON 2015), vol. 9198 of Lecture Notes in Computer Science, pp. 701-712. Springer, 2015. Full paper: arXiv:1504.08251 [cs.DS], 2015.
[C34]	Marvin Künnemann, Bodo Manthey. Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic. Proc. 42nd Int. Colloquium on Automata, Languages, and Programming (ICALP 2015), Part 1, vol. 9134 of Lecture Notes in Computer Science, pp. 859-871. Springer, 2015.
[C33]	Maurits de Graaf, Bodo Manthey. Probabilistic Analysis of Power Assignments. Proc. 39th Int. Symposium on Mathematical Foundations of Computer Science (MFCS 2014), Part II, vol. 8635 of Lecture Notes in Computer Science, pp. 201-212. Springer, 2014. Superseded by journal article [J33].
[C32]	Ruben Hoeksma, Bodo Manthey, Marc Uetz. Decomposition Algorithm for the Single Machine Scheduling Polytope. Proc. 3rd Int. Symposium on Combinatorial Optimization (ISCO 2014), vol. 8596 of Lecture Notes in Computer Science, pp. 280-291. Springer, 2014. Superseded by journal article [J32].
[C31]	Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul. Approximability of Connected Factors. Proc. 11th Workshop on Approximation and Online Algorithms (WAOA 2013), vol. 8447 of Lecture Notes in Computer Science, pp. 120-131. Springer, 2014. Superseded by journal article [J35].
[C30]	Bodo Manthey, Rianne Veenstra. Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise. Proc. 24th Int. Symposium on Algorithms and Computation (ISAAC 2013), vol. 8283 of Lecture Notes in Computer Science, pp. 579-589. Springer, 2013. Full, improved version.
[C29]	Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao. Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems. Proc. 38th Int. Symposium on Mathematical Foundations of Computer Science (MFCS 2013), vol. 8087 of Lecture Notes in Computer Science, pp. 219-230. Springer, 2013. Superseded by journal article [J30].
[C28]	Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin. Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching. Proc. 7th Int. Workshop Algorithms and Computation (WALCOM 2013), vol. 7748 of Lecture Notes in Computer Science, pp. 182-193. Springer, 2013. Invited to a special issue of Journal of Graph Algorithms and Applications [J28].
[C27]	Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin. Smoothed Analysis of the Successive Shortest Path Algorithm. Proc. 24th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 1180-1189. SIAM, 2013. Superseded by journal article [J31].
[C26]	Markus Bläser, Bodo Manthey. Smoothed Complexity Theory. Proc. 37th Int. Symposium on Mathematical Foundations of Computer Science (MFCS 2012), vol. 7464 of Lecture Notes of Computer Science, pp. 198-209. Springer, 2012. Superseded by journal article [J29].
[C25]	Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao. Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. Proc. 12th Int. Algorithms and Data Structures Symposium (WADS 2011), vol. 6844 of Lecture Notes in Computer Science, pp. 110-121. Springer, 2011. Superseded by journal article [J24].
[C24]	Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey. Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes. Proc. 38th Int. Colloquium on Automata, Languages and Programming (ICALP 2011), Part I, vol. 6755 of Lecture Notes in Computer Science, pp. 147-158. Springer, 2011. Superseded by journal article [J37].
[C23]	Bodo Manthey. Deterministic Algorithms for Multi-Criteria TSP. Proc. 8th Ann. Conference on Theory and Applications of Models of Computation (TAMC 2011), vol. 6648 of Lecture Notes in Computer Science, pp. 264-275. Springer, 2011. Superseded by journal article [J23].
[C22]	Bodo Manthey. Multi-Criteria TSP: Min and Max Combined. Proc. 7th Int. Workshop on Approximation and Online Algorithms (WAOA 2009), 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. Proc. 20th Int. Symposium on Algorithms and Computation (ISAAC 2009), vol. 5878 of Lecture Notes in Computer Science, pp. 1024-1033. Springer, 2009. Superseeded by journal article [J27].
[C20]	David Arthur, Bodo Manthey, Heiko Röglin. k-Means has Polynomial Smoothed Complexity. Proc. 50th Ann. IEEE Symposium on Foundations of Computer Science (FOCS 2009), 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. Proc. 15th Ann. Int. Computing and Combinatorics Conference (COCOON 2009), 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. Proc. 26th Int. Symposium on Theoretical Aspects of Computer Science (STACS 2009), vol. 3 of LIPIcs, pp. 637-648. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2009. Superseded by journal article [J21].
[C17]	Bodo Manthey, Heiko Röglin. Improved Smoothed Analysis of the k-Means Method. Proc. 20th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pp. 461-470. SIAM, 2009. Superseded by journal articles [J17] and [J27].
[C16]	Markus Bläser, Bodo Manthey, Oliver Putz. Approximating Multi-Criteria Max-TSP. Proc. 16th Ann. European Symposium on Algorithms (ESA 2008), vol. 5193 of Lecture Notes in Computer Science, pp. 185-197. Springer, 2008. Full paper: arXiv:0806.3668 [cs.DS], 2008. The results are superseded by journal article [J21].
[C15]	Bodo Manthey, Till Tantau. Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. Proc. 33rd Int. Symposium on Mathematical Foundations of Computer Science (MFCS 2008), 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. Proc. 33rd Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), 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. Proc. 4th Int. Workshop on Approximation and Online Algorithms (WAOA 2006), 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. Proc. 32nd Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006), 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. Proc. 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), 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. Proc. 3rd Int. Workshop on Approximation and Online Algorithms (WAOA 2005), 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. Proc. 16th Int. Symposium on Algorithms and Computation (ISAAC 2005), 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. Proc. 10th Int. Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2004), 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. Proc. 14th Int. Symposium on Algorithms and Computation (ISAAC 2003), 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. Proc. 4th ACM Conference on Electronic Commerce (EC 2003), pp. 194-195. ACM, 2003.
[C5]	Markus Bläser, Bodo Manthey. Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint. Proc. 13th Int. Symposium on Algorithms and Computation (ISAAC 2002), 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. Proc. 5th Int. Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), 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. Proc. 22nd Ann. Int. Cryptology Conference (CRYPTO 2002), 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. Proc. 9th Ann. European Symposium on Algorithms (ESA 2001), 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. Proc. 7th Ann. Int. Computing and Combinatorics Conference (COCOON 2001), 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
[O8]	Bodo Manthey, Claire Mathieu, Heiko Röglin, Eli Upfal. Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141). Dagstuhl Reports 7(4), 2017.
[O7]	Johann Hurink, Bodo Manthey. Editorial: 12th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2013). Discrete Applied Mathematics, 195, 2015. Special issue dedicated to CTW 2013, edited by Johann Hurink and Bodo Manthey.
[O6]	Bodo Manthey. Smoothed Analysis of Local Search Algorithms. Proc. 14th Int. Algorithms and Data Structures Symposium (WADS 2015), invited contribution, vol. 9214 of Lecture Notes in Computer Science, pp. 518-527. Springer, 2015.
[O5]	Maria-Florina Balcan, Bodo Manthey, Heiko Röglin, Tim Roughgarden. Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372). Dagstuhl Reports 4(9):30-49, 2015.
[O4]	Kamiel Cornelissen, Ruben Hoeksma, Johann Hurink, Bodo Manthey (eds.). Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2013). CTIT Workshop Proceedings WP 13-01, 2013.
[O3]	Bodo Manthey. Approximability of Cycle Covers and Smoothed Analysis of Binary Search Trees. Ausgezeichnete Informatikdissertationen 2005, vol. D-6 of GI-Edition – Lecture Notes in Informatics, pp. 57-66. Köllen, 2006.
[O2]	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.
[O1]	Martin Böhme, Rainer Hagenau, Jan Modersitzki, Bodo Siebert. Non-Linear Image Registration on PC-Clusters Using Parallel FFT Techniques. SIIM Technical Report A-02-08, University of Lübeck, 2002. Bodo Siebert is Bodo Manthey's birth name.

Bodo Manthey

Short CV

Teaching (only national courses)

Publications

Journal Articles

Conference Papers

Other Publications