default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBodo Manthey
Bodo Siebert
Person information
- affiliation: University of Twente, Enschede, Netherlands
- affiliation (former): Yale University, New Haven, CT, USA
- affiliation (former): Saarland University, Saarbrücken
- affiliation (PhD 2005): University of Lübeck, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c47]Bodo Manthey, Jesse van Rhijn
:
Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering. STACS 2024: 52:1-52:16- 2023
- [j45]Stefan Klootwijk, Bodo Manthey:
Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics. Algorithmica 85(12): 3793-3815 (2023) - [c46]Bodo Manthey, Jesse van Rhijn:
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP. ISAAC 2023: 52:1-52:16 - [c45]Bodo Manthey, Jesse van Rhijn:
Approximation Ineffectiveness of a Tour-Untangling Heuristic. WAOA 2023: 1-13 - [i37]Bodo Manthey, Jesse van Rhijn:
Approximation Ineffectiveness of a Tour-Untangling Heuristic. CoRR abs/2302.11264 (2023) - [i36]Marvin Künnemann, Bodo Manthey, Rianne Veenstra:
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise. CoRR abs/2308.00306 (2023) - [i35]Bodo Manthey, Jesse van Rhijn:
Worst-Case and Smoothed Analysis of Hartigan's Method for k-Means Clustering. CoRR abs/2309.10368 (2023) - [i34]Bodo Manthey, Nils Morawietz, Jesse van Rhijn, Frank Sommer:
Complexity of Local Search for Euclidean Clustering Problems. CoRR abs/2312.14916 (2023) - 2022
- [i33]Bodo Manthey, Jesse van Rhijn:
Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP. CoRR abs/2208.11444 (2022) - [i32]Bodo Manthey, Jesse van Rhijn:
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP. CoRR abs/2211.16908 (2022) - 2021
- [j44]Bodo Manthey, Johann L. Hurink:
Preface: 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2019). Discret. Appl. Math. 303: 1 (2021) - [j43]Winfried Hochstättler, Johann L. Hurink, Bodo Manthey, Daniël Paulusma, Britta Peis, Georg Still:
In Memoriam Walter Kern. Discret. Appl. Math. 303: 2-3 (2021) - [j42]Bodo Manthey, Victor M. J. J. Reijnders:
Probabilistic properties of highly connected random geometric graphs. Discret. Appl. Math. 305: 366-376 (2021) - [j41]Stefan Klootwijk, Bodo Manthey, Sander K. Visser:
Probabilistic analysis of optimization problems on generalized random shortest path metrics. Theor. Comput. Sci. 866: 107-122 (2021) - 2020
- [j40]Kamiel Cornelissen, Bodo Manthey:
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. J. Graph Algorithms Appl. 24(3): 397-421 (2020) - [c44]Stefan Klootwijk, Bodo Manthey:
Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics. AofA 2020: 19:1-19:16 - [p2]Bodo Manthey:
Smoothed Analysis of Local Search. Beyond the Worst-Case Analysis of Algorithms 2020: 285-308
2010 – 2019
- 2019
- [c43]Stefan Klootwijk, Bodo Manthey:
Probabilistic Analysis of Facility Location on Random Shortest Path Metrics. CiE 2019: 37-49 - [c42]Stefan Klootwijk, Bodo Manthey, Sander K. Visser:
Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics. WALCOM 2019: 108-120 - [i31]Stefan Klootwijk, Bodo Manthey:
Probabilistic Analysis of Facility Location on Random Shortest Path Metrics. CoRR abs/1903.11980 (2019) - 2018
- [j39]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): 3132-3157 (2018) - [j38]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): 441-464 (2018) - [j37]Bodo Manthey, Matthijs B. Tijink:
Perturbation resilience for the facility location problem. Oper. Res. Lett. 46(2): 215-218 (2018) - [j36]Kamiel Cornelissen, Bodo Manthey:
Belief propagation for the maximum-weight independent set and minimum spanning tree problems. Theor. Comput. Sci. 738: 53-64 (2018) - [c41]Bodo Manthey, Victor M. J. J. Reijnders:
Probabilistic Properties of Highly Connected Random Geometric Graphs. CALDAM 2018: 59-72 - [i30]Stefan Klootwijk, Bodo Manthey, Sander K. Visser:
Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics. CoRR abs/1810.11232 (2018) - 2017
- [j35]Walter Kern, Bodo Manthey:
Approximating bounded-degree spanning trees and connected factors with leaves. Oper. Res. Lett. 45(2): 115-118 (2017) - [j34]Maurits de Graaf, Bodo Manthey:
Probabilistic analysis of power assignments. Random Struct. Algorithms 51(3): 483-505 (2017) - [i29]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): 1-22 (2017) - 2016
- [j33]Ruben Hoeksma, Bodo Manthey, Marc Uetz:
Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope. Discret. Appl. Math. 215: 136-145 (2016) - [i28]Walter Kern, Bodo Manthey, Marc Uetz:
Note on VCG vs. Price Raising for Matching Markets. CoRR abs/1604.04157 (2016) - 2015
- [j32]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) - [j31]Johann L. Hurink, Bodo Manthey:
12th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2013). Discret. Appl. Math. 195: 1 (2015) - [j30]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): 1798-1819 (2015) - [j29]Markus Bläser, Bodo Manthey:
Smoothed Complexity Theory. ACM Trans. Comput. Theory 7(2): 6:1-6:21 (2015) - [c40]Kamiel Cornelissen, Bodo Manthey:
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. COCOON 2015: 701-712 - [c39]Marvin Künnemann, Bodo Manthey:
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic. ICALP (1) 2015: 859-871 - [c38]Bodo Manthey:
Smoothed Analysis of Local Search Algorithms. WADS 2015: 518-527 - [c37]Bodo Manthey, Marten Waanders:
Approximation Algorithms for k-Connected Graph Factors. WAOA 2015: 1-12 - [i27]Marvin Künnemann, Bodo Manthey:
On the Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP. CTW 2015: 1-4 - [i26]Kamiel Cornelissen, Bodo Manthey:
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. CTW 2015: 157-160 - [i25]Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin, Clemens Rösner:
Smoothed Analysis of the Successive Shortest Path Algorithm. CoRR abs/1501.05493 (2015) - [i24]Kamiel Cornelissen, Bodo Manthey:
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. CoRR abs/1504.08251 (2015) - 2014
- [c36]Ruben Hoeksma, Bodo Manthey, Marc Uetz:
Decomposition Algorithm for the Single Machine Scheduling Polytope. ISCO 2014: 280-291 - [c35]Maurits de Graaf, Bodo Manthey:
Probabilistic Analysis of Power Assignments. MFCS (2) 2014: 201-212 - [i23]Maurits de Graaf, Bodo Manthey:
Probabilistic Analysis of Power Assignments. CoRR abs/1403.5882 (2014) - [i22]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 (2014) - 2013
- [j28]Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao:
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. Algorithmica 66(2): 397-418 (2013) - [j27]Matthijs Bomhoff, Bodo Manthey:
Bisimplicial edges in bipartite graphs. Discret. Appl. Math. 161(12): 1699-1706 (2013) - [j26]Bodo Manthey, Kai Plociennik:
Approximating independent set in perturbed graphs. Discret. Appl. Math. 161(12): 1761-1768 (2013) - [j25]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): 647-670 (2013) - [j24]Bodo Manthey, Heiko Röglin:
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences. J. Comput. Geom. 4(1): 94-132 (2013) - [c34]Bodo Manthey, Rianne Veenstra:
Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise. ISAAC 2013: 579-589 - [c33]Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao:
Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems. MFCS 2013: 219-230 - [c32]Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin:
Smoothed Analysis of the Successive Shortest Path Algorithm. SODA 2013: 1180-1189 - [c31]Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin:
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching. WALCOM 2013: 182-193 - [c30]Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul:
Approximability of Connected Factors. WAOA 2013: 120-131 - [e1]Kamiel Cornelissen, Ruben Hoeksma, Johann L. Hurink, Bodo Manthey:
12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Enschede, Netherlands, May 21-23, 2013. CTIT Workshop Proceedings WP 13-01, 2013 [contents] - [i21]Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin:
Smoothed analysis of the successive shortest path algorithm. CTW 2013: 27-30 - [i20]Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao:
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems. CoRR abs/1306.3030 (2013) - [i19]Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul:
Approximability of Connected Factors. CoRR abs/1310.2387 (2013) - 2012
- [j23]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) - [j22]Bodo Manthey:
Deterministic algorithms for multi-criteria Max-TSP. Discret. Appl. Math. 160(15): 2277-2285 (2012) - [j21]Bodo Manthey:
Multi-criteria TSP: Min and max combined. Oper. Res. Lett. 40(1): 36-38 (2012) - [j20]Bodo Manthey:
On approximating multicriteria TSP. ACM Trans. Algorithms 8(2): 17:1-17:18 (2012) - [j19]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): 30:1-30:28 (2012) - [c29]Christian Engels, Bodo Manthey, B. V. Raghavendra Rao:
Random Shortest Path Metrics with Applications. CTW 2012: 121-124 - [c28]Markus Bläser, Bodo Manthey:
Smoothed Complexity Theory. MFCS 2012: 198-209 - [i18]Markus Bläser, Bodo Manthey:
Smoothed Complexity Theory. CoRR abs/1202.1936 (2012) - [i17]Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin:
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching. CoRR abs/1211.3299 (2012) - 2011
- [j18]Bodo Manthey, Heiko Röglin:
Smoothed Analysis: Analysis of Algorithms Beyond Worst Case. it Inf. Technol. 53(6): 280-286 (2011) - [j17]David Arthur, Bodo Manthey, Heiko Röglin:
Smoothed Analysis of the k-Means Method. J. ACM 58(5): 19:1-19:31 (2011) - [j16]Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Privacy in Non-private Environments. Theory Comput. Syst. 48(1): 211-245 (2011) - [c27]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: 147-158 - [c26]Bodo Manthey:
Deterministic Algorithms for Multi-criteria TSP. TAMC 2011: 264-275 - [c25]Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao:
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. WADS 2011: 110-121 - 2010
- [c24]Matthijs Bomhoff, Bodo Manthey:
Bisimplicial Edges in Bipartite Graphs. CTW 2010: 29-32 - [c23]Bodo Manthey, Kai Plociennik:
Approximating Independent Set in Semi-Random Graphs. CTW 2010: 119-122
2000 – 2009
- 2009
- [j15]Bodo Manthey, L. Shankar Ram:
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems. Algorithmica 53(1): 69-88 (2009) - [j14]Jan Arpe, Bodo Manthey:
Approximability of Minimum AND-Circuits. Algorithmica 53(3): 337-357 (2009) - [j13]Bodo Manthey:
Minimum-weight cycle covers and their approximability. Discret. Appl. Math. 157(7): 1470-1480 (2009) - [j12]Christian Engels, Bodo Manthey:
Average-case approximation ratio of the 2-opt algorithm for the TSP. Oper. Res. Lett. 37(2): 83-84 (2009) - [c22]Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi:
On Smoothed Analysis of Quicksort and Hoare's Find. COCOON 2009: 158-167 - [c21]David Arthur, Bodo Manthey, Heiko Röglin:
k-Means Has Polynomial Smoothed Complexity. FOCS 2009: 405-414 - [c20]Bodo Manthey, Heiko Röglin:
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences. ISAAC 2009: 1024-1033 - [c19]Bodo Manthey, Heiko Röglin:
Improved smoothed analysis of the k-means method. SODA 2009: 461-470 - [c18]Bodo Manthey:
On Approximating Multi-Criteria TSP. STACS 2009: 637-648 - [c17]Bodo Manthey:
Multi-Criteria TSP: Min and Max Combined. WAOA 2009: 205-216 - [i16]David Arthur, Bodo Manthey, Heiko Röglin:
k-Means has Polynomial Smoothed Complexity. CoRR abs/0904.1113 (2009) - [i15]Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi:
On Smoothed Analysis of Quicksort and Hoare's Find. CoRR abs/0904.3898 (2009) - 2008
- [j11]Markus Bläser, Thomas Heynen, Bodo Manthey:
Adding cardinality constraints to integer programs with applications to maximum satisfiability. Inf. Process. Lett. 105(5): 194-198 (2008) - [j10]Bodo Manthey:
On Approximating Restricted Cycle Covers. SIAM J. Comput. 38(1): 181-206 (2008) - [c16]Markus Bläser, Bodo Manthey, Oliver Putz:
Approximating Multi-criteria Max-TSP. ESA 2008: 185-197 - [c15]Bodo Manthey, Till Tantau:
Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise. MFCS 2008: 467-478 - [i14]Markus Bläser, Bodo Manthey, Oliver Putz:
Approximating Multi-Criteria Max-TSP. CoRR abs/0806.3668 (2008) - [i13]Bodo Manthey, Heiko Röglin:
Improved Smoothed Analysis of the k-Means Method. CoRR abs/0809.1715 (2008) - 2007
- [j9]Bodo Manthey, Rüdiger Reischuk:
Smoothed analysis of binary search trees. Theor. Comput. Sci. 378(3): 292-315 (2007) - [c14]Bodo Manthey:
Minimum-Weight Cycle Covers and Their Approximability. WG 2007: 178-189 - [i12]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 - [i11]Bodo Manthey:
Approximate Pareto Curves for the Asymmetric Traveling Salesman Problem. CoRR abs/0711.2157 (2007) - [i10]Bodo Manthey:
On Approximating Restricted Cycle Covers. Electron. Colloquium Comput. Complex. TR07 (2007) - [i9]Bodo Manthey, Till Tantau:
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j8]Markus Bläser, Bodo Manthey, Jirí Sgall:
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discrete Algorithms 4(4): 623-632 (2006) - [j7]Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Private Computation: k-Connected versus 1-Connected Networks. J. Cryptol. 19(3): 341-357 (2006) - [c13]Jan Arpe, Bodo Manthey:
Approximability of Minimum AND-Circuits. SWAT 2006: 292-303 - [c12]Bodo Manthey, L. Shankar Ram:
Approximation Algorithms for Multi-criteria Traveling Salesman Problems. WAOA 2006: 302-315 - [c11]Bodo Manthey:
Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions. WG 2006: 336-347 - [i8]Jan Arpe, Bodo Manthey:
Approximability of Minimum AND-Circuits. Complexity of Boolean Functions 2006 - [i7]Bodo Manthey, L. Shankar Ram:
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems. CoRR abs/cs/0606040 (2006) - [i6]Bodo Manthey:
Minimum-weight Cycle Covers and Their Approximability. CoRR abs/cs/0609103 (2006) - [i5]Jan Arpe, Bodo Manthey:
Approximability of Minimum AND-Circuits. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [b1]Bodo Manthey:
Approximability of cycle covers and smoothed analysis of binary search trees. Universität Lübeck, 2005, pp. I-XI, 1-117 - [j6]Markus Bläser, Bodo Manthey:
Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One. Algorithmica 42(2): 121-139 (2005) - [j5]Bodo Manthey:
Non-approximability of weighted multiple sequence alignment for arbitrary metrics. Inf. Process. Lett. 95(3): 389-395 (2005) - [j4]Bodo Manthey, Rüdiger Reischuk:
The intractability of computing the Hamming distance. Theor. Comput. Sci. 337(1-3): 331-346 (2005) - [c10]Bodo Manthey, Rüdiger Reischuk:
Smoothed Analysis of Binary Search Trees. ISAAC 2005: 483-492 - [c9]Bodo Manthey:
On Approximating Restricted Cycle Covers. WAOA 2005: 282-295 - [p1]Bodo Manthey:
Approximability of cycle covers and smoothed analysis of binary search trees. Ausgezeichnete Informatikdissertationen 2005: 57-66 - [i4]Bodo Manthey:
On Approximating Restricted Cycle Covers. CoRR abs/cs/0504038 (2005) - [i3]Bodo Manthey, Rüdiger Reischuk:
Smoothed Analysis of the Height of Binary Search Trees. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j3]Maciej Liskiewicz, Bodo Manthey:
New lower and upper bounds for the competitive ratio of transmission protocols. Inf. Process. Lett. 89(6): 297-301 (2004) - [c8]Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Privacy in Non-private Environments. ASIACRYPT 2004: 137-151 - 2003
- [j2]Martin Böhme, Bodo Manthey:
The Computational Power of Compiling C++. Bull. EATCS 81: 264-270 (2003)