Bodo Manthey

According to our database, Bodo Manthey authored at least 89 papers between 2001 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise.

Marvin Künnemann, Bodo Manthey, Rianne Veenstra

Algorithmica, November, 2025

Playing Snake on a Graph.

Denise Graafsma, Bodo Manthey, Alexander Skopalik

CoRR, June, 2025

Convergence and Running Time of Time-dependent Ant Colony Algorithms.

Bodo Manthey, Jesse van Rhijn, Ashkan Safari, Tjark Vredeveld

CoRR, January, 2025

Performance of efficient variants of the 2-Opt heuristic for the traveling salesperson problem.

Bodo Manthey, Jesse van Rhijn

Discret. Appl. Math., 2025

Counting Locally Optimal Tours in the TSP.

Bodo Manthey, Jesse van Rhijn

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

2024

Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering.

Bodo Manthey, Jesse van Rhijn

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Complexity of Local Search for Euclidean Clustering Problems.

Bodo Manthey, Nils Morawietz, Jesse van Rhijn, Frank Sommer

Proceedings of the 35th International Symposium on Algorithms and Computation, 2024

2023

Worst-Case and Smoothed Analysis of Hartigan's Method for k-Means Clustering.

Bodo Manthey, Jesse van Rhijn

CoRR, 2023

Approximation Ineffectiveness of a Tour-Untangling Heuristic.

Bodo Manthey, Jesse van Rhijn

Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

Improved Smoothed Analysis of 2-Opt for the Euclidean TSP.

Bodo Manthey, Jesse van Rhijn

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

2022

Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP.

Bodo Manthey, Jesse van Rhijn

CoRR, 2022

2021

Preface: 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2019).

Bodo Manthey, Johann L. Hurink

Discret. Appl. Math., 2021

In Memoriam Walter Kern.

Winfried Hochstättler, Johann L. Hurink, Bodo Manthey, Daniël Paulusma, Britta Peis, Georg Still

Discret. Appl. Math., 2021

2020

Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics.

Stefan Klootwijk, Bodo Manthey

Proceedings of the 31st International Conference on Probabilistic, 2020

Smoothed Analysis of Local Search.

Bodo Manthey

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics.

Stefan Klootwijk, Bodo Manthey, Sander K. Visser

Proceedings of the WALCOM: Algorithms and Computation - 13th International Conference, 2019

Probabilistic Analysis of Facility Location on Random Shortest Path Metrics.

Stefan Klootwijk, Bodo Manthey

Proceedings of the Computing with Foresight and Industry, 2019

2018

Belief propagation for the maximum-weight independent set and minimum spanning tree problems.

Kamiel Cornelissen, Bodo Manthey

Theor. Comput. Sci., 2018

Perturbation resilience for the facility location problem.

Bodo Manthey, Matthijs B. Tijink

Oper. Res. Lett., 2018

Approximation Algorithms for Connected Graph Factors of Minimum Weight.

Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul, Marten Waanders

Theory Comput. Syst., 2018

Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions.

Endre Boros, Khaled M. Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey

Algorithmica, 2018

Probabilistic Properties of Highly Connected Random Geometric Graphs.

Bodo Manthey, Victor M. J. J. Reijnders

Proceedings of the Algorithms and Discrete Applied Mathematics, 2018

2017

Approximating bounded-degree spanning trees and connected factors with leaves.

Walter Kern, Bodo Manthey

Oper. Res. Lett., 2017

Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141).

Bodo Manthey, Claire Mathieu, Heiko Röglin, Eli Upfal

Dagstuhl Reports, 2017

2016

Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope.

Ruben Hoeksma, Bodo Manthey, Marc Uetz

Discret. Appl. Math., 2016

Note on VCG vs. Price Raising for Matching Markets.

Walter Kern, Bodo Manthey, Marc Uetz

CoRR, 2016

2015

Smoothed Analysis of the Successive Shortest Path Algorithm.

Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin, Clemens Rösner

SIAM J. Comput., 2015

12th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2013).

Johann L. Hurink, Bodo Manthey

Discret. Appl. Math., 2015

Approximation Algorithms for k-Connected Graph Factors.

Bodo Manthey, Marten Waanders

Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

Smoothed Analysis of Local Search Algorithms.

Bodo Manthey

Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic.

Marvin Künnemann, Bodo Manthey

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

On the Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP.

Marvin Künnemann, Bodo Manthey

Proceedings of the 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2015

Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm.

Kamiel Cornelissen, Bodo Manthey

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014

Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372).

Maria-Florina Balcan, Bodo Manthey, Heiko Röglin, Tim Roughgarden

Dagstuhl Reports, 2014

Probabilistic Analysis of Power Assignments.

Maurits de Graaf, Bodo Manthey

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Decomposition Algorithm for the Single Machine Scheduling Polytope.

Ruben Hoeksma, Bodo Manthey, Marc Uetz

Proceedings of the Combinatorial Optimization - Third International Symposium, 2014

2013

Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences.

Bodo Manthey, Heiko Röglin

J. Comput. Geom., 2013

Approximating independent set in perturbed graphs.

Bodo Manthey, Kai Plociennik

Discret. Appl. Math., 2013

Approximability of Connected Factors.

Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul

Proceedings of the Approximation and Online Algorithms - 11th International Workshop, 2013

Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching.

Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin

Proceedings of the WALCOM: Algorithms and Computation, 7th International Workshop, 2013

Smoothed Analysis of the Successive Shortest Path Algorithm.

Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems.

Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise.

Bodo Manthey, Rianne Veenstra

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

2012

On approximating multicriteria TSP.

Bodo Manthey

ACM Trans. Algorithms, 2012

Smoothed analysis of left-to-right maxima with applications.

Valentina Damerow, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, Till Tantau

ACM Trans. Algorithms, 2012

Deterministic algorithms for multi-criteria Max-TSP.

Bodo Manthey

Discret. Appl. Math., 2012

Smoothed Complexity Theory.

Markus Bläser, Bodo Manthey

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Random Shortest Path Metrics with Applications.

Christian Engels, Bodo Manthey, B. V. Raghavendra Rao

Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2012

2011

Smoothed Analysis of the k-Means Method.

David Arthur, Bodo Manthey, Heiko Röglin

J. ACM, 2011

Smoothed Analysis: Analysis of Algorithms Beyond Worst Case.

Bodo Manthey, Heiko Röglin

it Inf. Technol., 2011

Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.

Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Deterministic Algorithms for Multi-criteria TSP.

Bodo Manthey

Proceedings of the Theory and Applications of Models of Computation, 2011

Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes.

Endre Boros, Khaled M. Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Approximating Independent Set in Semi-Random Graphs.

Bodo Manthey, Kai Plociennik

Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2010

Bisimplicial Edges in Bipartite Graphs.

Matthijs Bomhoff, Bodo Manthey

Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2010

2009

Average-case approximation ratio of the 2-opt algorithm for the TSP.

Christian Engels, Bodo Manthey

Oper. Res. Lett., 2009

Multi-Criteria TSP: Min and Max Combined.

Bodo Manthey

Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

On Approximating Multi-Criteria TSP.

Bodo Manthey

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Improved smoothed analysis of the <i>k</i>-means method.

Bodo Manthey, Heiko Röglin

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Worst-Case and Smoothed Analysis of <i>k</i>-Means Clustering with Bregman Divergences.

Bodo Manthey, Heiko Röglin

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

k-Means Has Polynomial Smoothed Complexity.

David Arthur, Bodo Manthey, Heiko Röglin

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

On Smoothed Analysis of Quicksort and Hoare's Find.

Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi

Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

2008

Adding cardinality constraints to integer programs with applications to maximum satisfiability.

Markus Bläser, Thomas Heynen, Bodo Manthey

Inf. Process. Lett., 2008

Improved Smoothed Analysis of the k-Means Method

Bodo Manthey, Heiko Röglin

CoRR, 2008

Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise.

Bodo Manthey, Till Tantau

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

Approximating Multi-criteria Max-TSP.

Markus Bläser, Bodo Manthey, Oliver Putz

Proceedings of the Algorithms, 2008

2007

Approximate Pareto Curves for the Asymmetric Traveling Salesman Problem

Bodo Manthey

CoRR, 2007

Minimum-Weight Cycle Covers and Their Approximability.

Bodo Manthey

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2007

2006

An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality.

Markus Bläser, Bodo Manthey, Jirí Sgall

J. Discrete Algorithms, 2006

Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions.

Bodo Manthey

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

Approximation Algorithms for Multi-criteria Traveling Salesman Problems.

Bodo Manthey, L. Shankar Ram

Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

Approximability of Minimum AND-Circuits.

Jan Arpe, Bodo Manthey

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

2005

Non-approximability of weighted multiple sequence alignment for arbitrary metrics.

Bodo Manthey

Inf. Process. Lett., 2005

Smoothed Analysis of the Height of Binary Search Trees

Bodo Manthey, Rüdiger Reischuk

Electron. Colloquium Comput. Complex., 2005

Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One.

Markus Bläser, Bodo Manthey

Algorithmica, 2005

On Approximating Restricted Cycle Covers.

Bodo Manthey

Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

Smoothed Analysis of Binary Search Trees.

Bodo Manthey, Rüdiger Reischuk

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Approximability of cycle covers and smoothed analysis of binary search trees.

Bodo Manthey

Proceedings of the Ausgezeichnete Informatikdissertationen 2005, 2005

Approximability of cycle covers and smoothed analysis of binary search trees.

Bodo Manthey

PhD thesis, 2005

2004

New lower and upper bounds for the competitive ratio of transmission protocols.

Maciej Liskiewicz, Bodo Manthey

Inf. Process. Lett., 2004

Privacy in Non-private Environments.

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

Proceedings of the Advances in Cryptology, 2004

2003

The Computational Power of Compiling C++.

Martin Böhme, Bodo Manthey

Bull. EATCS, 2003

Budget balanced mechanisms for the multicast pricing problem with rates.

Markus Bläser, Bodo Manthey

Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

The Intractability of Computing the Hamming Distance.

Bodo Manthey, Rüdiger Reischuk

Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2002

Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint.

Markus Bläser, Bodo Manthey

Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

Private Computation - k-Connected versus 1-Connected Networks.

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Siebert

Proceedings of the Advances in Cryptology, 2002

Two Approximation Algorithms for 3-Cycle Covers.

Markus Bläser, Bodo Manthey

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001

Computing Cycle Covers without Short Cycles.

Markus Bläser, Bodo Siebert

Proceedings of the Algorithms, 2001

Non-approximability of Weighted Multiple Sequence Alignment.

Bodo Siebert

Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001