Bodo Manthey

ORCID

Publication Activity (10 Years)

Years Active: 2002-2024
Publications (10 Years): 30

Top Venues

Universität Lübeck (PHD)

Education History

Universität Lübeck

PHD

Publications

Bodo Manthey, Jesse van Rhijn
Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering. STACS (2024)
Marvin Künnemann, Bodo Manthey, Rianne Veenstra
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise. CoRR (2023)
Bodo Manthey, Nils Morawietz, Jesse van Rhijn, Frank Sommer
Complexity of Local Search for Euclidean Clustering Problems. CoRR (2023)
Bodo Manthey, Jesse van Rhijn
Approximation Ineffectiveness of a Tour-Untangling Heuristic. WAOA (2023)
Bodo Manthey, Jesse van Rhijn
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP. ISAAC (2023)
Bodo Manthey, Jesse van Rhijn
Worst-Case and Smoothed Analysis of Hartigan's Method for k-Means Clustering. CoRR (2023)
Bodo Manthey, Jesse van Rhijn
Approximation Ineffectiveness of a Tour-Untangling Heuristic. CoRR (2023)
Stefan Klootwijk, Bodo Manthey
Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics. Algorithmica 85 (12) (2023)
Bodo Manthey, Jesse van Rhijn
Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP. CoRR (2022)
Bodo Manthey, Jesse van Rhijn
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP. CoRR (2022)
Winfried Hochstättler, Johann L. Hurink, Bodo Manthey, Daniël Paulusma, Britta Peis, Georg Still
In Memoriam Walter Kern. Discret. Appl. Math. 303 (2021)
Stefan Klootwijk, Bodo Manthey, Sander K. Visser
Probabilistic analysis of optimization problems on generalized random shortest path metrics. Theor. Comput. Sci. 866 (2021)
Bodo Manthey, Victor M. J. J. Reijnders
Probabilistic properties of highly connected random geometric graphs. Discret. Appl. Math. 305 (2021)
Bodo Manthey, Johann L. Hurink
Preface: 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2019). Discret. Appl. Math. 303 (2021)
Kamiel Cornelissen, Bodo Manthey
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. J. Graph Algorithms Appl. 24 (3) (2020)
Stefan Klootwijk, Bodo Manthey
Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics. AofA (2020)
Stefan Klootwijk, Bodo Manthey, Sander K. Visser
Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics. WALCOM (2019)
Stefan Klootwijk, Bodo Manthey
Probabilistic Analysis of Facility Location on Random Shortest Path Metrics. CoRR (2019)
Stefan Klootwijk, Bodo Manthey
Probabilistic Analysis of Facility Location on Random Shortest Path Metrics. CiE (2019)
Bodo Manthey, Victor M. J. J. Reijnders
Probabilistic Properties of Highly Connected Random Geometric Graphs. CALDAM (2018)
Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul, Marten Waanders
Approximation Algorithms for Connected Graph Factors of Minimum Weight. Theory Comput. Syst. 62 (2) (2018)
Stefan Klootwijk, Bodo Manthey, Sander K. Visser
Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics. CoRR (2018)
Endre Boros, Khaled M. Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey
Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions. Algorithmica 80 (11) (2018)
Bodo Manthey, Matthijs B. Tijink
Perturbation resilience for the facility location problem. Oper. Res. Lett. 46 (2) (2018)
Kamiel Cornelissen, Bodo Manthey
Belief propagation for the maximum-weight independent set and minimum spanning tree problems. Theor. Comput. Sci. 738 (2018)
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)
Maurits de Graaf, Bodo Manthey
Probabilistic analysis of power assignments. Random Struct. Algorithms 51 (3) (2017)
Walter Kern, Bodo Manthey
Approximating bounded-degree spanning trees and connected factors with leaves. Oper. Res. Lett. 45 (2) (2017)
Ruben Hoeksma, Bodo Manthey, Marc Uetz
Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope. Discret. Appl. Math. 215 (2016)
Walter Kern, Bodo Manthey, Marc Uetz
Note on VCG vs. Price Raising for Matching Markets. CoRR (2016)
Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems. Algorithmica 73 (1) (2015)
Bodo Manthey
Smoothed Analysis of Local Search Algorithms. WADS (2015)
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin, Clemens Rösner
Smoothed Analysis of the Successive Shortest Path Algorithm. CoRR (2015)
Bodo Manthey, Marten Waanders
Approximation Algorithms for k-Connected Graph Factors. WAOA (2015)
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin, Clemens Rösner
Smoothed Analysis of the Successive Shortest Path Algorithm. SIAM J. Comput. 44 (6) (2015)
Marvin Künnemann, Bodo Manthey
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic. ICALP (1) (2015)
Johann L. Hurink, Bodo Manthey
12th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2013). Discret. Appl. Math. 195 (2015)
Markus Bläser, Bodo Manthey
Smoothed Complexity Theory. ACM Trans. Comput. Theory 7 (2) (2015)
Kamiel Cornelissen, Bodo Manthey
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. CTW (2015)
Kamiel Cornelissen, Bodo Manthey
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. CoRR (2015)
Marvin Künnemann, Bodo Manthey
On the Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP. CTW (2015)
Kamiel Cornelissen, Bodo Manthey
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. COCOON (2015)
Maurits de Graaf, Bodo Manthey
Probabilistic Analysis of Power Assignments. MFCS (2) (2014)
Ruben Hoeksma, Bodo Manthey, Marc Uetz
Decomposition Algorithm for the Single Machine Scheduling Polytope. ISCO (2014)
Maria-Florina Balcan, Bodo Manthey, Heiko Röglin, Tim Roughgarden
Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372). Dagstuhl Reports 4 (9) (2014)
Maurits de Graaf, Bodo Manthey
Probabilistic Analysis of Power Assignments. CoRR (2014)
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin
Smoothed analysis of the successive shortest path algorithm. CTW (2013)
Bodo Manthey, Kai Plociennik
Approximating independent set in perturbed graphs. Discret. Appl. Math. 161 (12) (2013)
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching. J. Graph Algorithms Appl. 17 (6) (2013)
Bodo Manthey, Heiko Röglin
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences. J. Comput. Geom. 4 (1) (2013)
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching. WALCOM (2013)
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin
Smoothed Analysis of the Successive Shortest Path Algorithm. SODA (2013)
Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. Algorithmica 66 (2) (2013)
Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul
Approximability of Connected Factors. WAOA (2013)
Matthijs Bomhoff, Bodo Manthey
Bisimplicial edges in bipartite graphs. Discret. Appl. Math. 161 (12) (2013)
Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems. CoRR (2013)
Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul
Approximability of Connected Factors. CoRR (2013)
Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems. MFCS (2013)
Bodo Manthey, Rianne Veenstra
Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise. ISAAC (2013)
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching CoRR (2012)
Markus Bläser, Bodo Manthey
Smoothed Complexity Theory CoRR (2012)
Bodo Manthey
Deterministic algorithms for multi-criteria Max-TSP. Discret. Appl. Math. 160 (15) (2012)
Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi
On Smoothed Analysis of Quicksort and Hoare's Find. Algorithmica 62 (3-4) (2012)
Markus Bläser, Bodo Manthey
Smoothed Complexity Theory. MFCS (2012)
Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
Random Shortest Path Metrics with Applications. CTW (2012)
Bodo Manthey
Multi-criteria TSP: Min and max combined. Oper. Res. Lett. 40 (1) (2012)
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 Trans. Algorithms 8 (3) (2012)
Bodo Manthey
On approximating multicriteria TSP. ACM Trans. Algorithms 8 (2) (2012)
David Arthur, Bodo Manthey, Heiko Röglin
Smoothed Analysis of the k-Means Method. J. ACM 58 (5) (2011)
Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. WADS (2011)
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
Privacy in Non-private Environments. Theory Comput. Syst. 48 (1) (2011)
Endre Boros, Khaled M. Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey
Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes. ICALP (1) (2011)
Bodo Manthey
Deterministic Algorithms for Multi-criteria TSP. TAMC (2011)
Bodo Manthey, Heiko Röglin
Smoothed Analysis: Analysis of Algorithms Beyond Worst Case. it Inf. Technol. 53 (6) (2011)
Matthijs Bomhoff, Bodo Manthey
Bisimplicial Edges in Bipartite Graphs. CTW (2010)
Bodo Manthey, Kai Plociennik
Approximating Independent Set in Semi-Random Graphs. CTW (2010)
Bodo Manthey
On Approximating Multi-Criteria TSP. STACS (2009)
Bodo Manthey
Multi-Criteria TSP: Min and Max Combined. WAOA (2009)
Jan Arpe, Bodo Manthey
Approximability of Minimum AND-Circuits. Algorithmica 53 (3) (2009)
Bodo Manthey
Minimum-weight cycle covers and their approximability. Discret. Appl. Math. 157 (7) (2009)
Christian Engels, Bodo Manthey
Average-case approximation ratio of the 2-opt algorithm for the TSP. Oper. Res. Lett. 37 (2) (2009)
David Arthur, Bodo Manthey, Heiko Röglin
k-Means Has Polynomial Smoothed Complexity. FOCS (2009)
David Arthur, Bodo Manthey, Heiko Röglin
k-Means has Polynomial Smoothed Complexity CoRR (2009)
Bodo Manthey, L. Shankar Ram
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems. Algorithmica 53 (1) (2009)
Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi
On Smoothed Analysis of Quicksort and Hoare's Find. COCOON (2009)
Bodo Manthey, Heiko Röglin
-means method. SODA (2009)
Bodo Manthey, Heiko Röglin
-Means Clustering with Bregman Divergences. ISAAC (2009)
Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi
On Smoothed Analysis of Quicksort and Hoare's Find CoRR (2009)
Bodo Manthey, Till Tantau
Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise. MFCS (2008)
Bodo Manthey
On Approximating Restricted Cycle Covers. SIAM J. Comput. 38 (1) (2008)
Markus Bläser, Thomas Heynen, Bodo Manthey
Adding cardinality constraints to integer programs with applications to maximum satisfiability. Inf. Process. Lett. 105 (5) (2008)
Markus Bläser, Bodo Manthey, Oliver Putz
Approximating Multi-criteria Max-TSP. ESA (2008)
Bodo Manthey, Heiko Röglin
Improved Smoothed Analysis of the k-Means Method CoRR (2008)
Markus Bläser, Bodo Manthey, Oliver Putz
Approximating Multi-Criteria Max-TSP CoRR (2008)
Bodo Manthey, Till Tantau
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Bodo Manthey, Rüdiger Reischuk
Smoothed analysis of binary search trees. Theor. Comput. Sci. 378 (3) (2007)
Bodo Manthey
Minimum-Weight Cycle Covers and Their Approximability. WG (2007)
Bodo Manthey, Till Tantau
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. Electron. Colloquium Comput. Complex. 14 (039) (2007)
Bodo Manthey
On Approximating Restricted Cycle Covers. Electron. Colloquium Comput. Complex. 14 (011) (2007)
Bodo Manthey
Approximate Pareto Curves for the Asymmetric Traveling Salesman Problem CoRR (2007)

Bodo Manthey.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Bodo Manthey