No photo of Bodo Manthey
Contact Expert

View Scopus Profile

Bodo Manthey

dr.

 https://orcid.org/0000-0001-6278-5059
20022024

Research activity per year

Filter
Conference contribution

Search results

  • 2024

    Complexity of Local Search for Euclidean Clustering Problems

    Manthey, B., Morawietz, N., van Rhijn, J. & Sommer, F., 4 Dec 2024, 35th International Symposium on Algorithms and Computation, ISAAC 2024. Mestre, J. & Wirth, A. (eds.). Dagstuhl, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 322).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
    14 Downloads (Pure)

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

    Manthey, B. & van Rhijn, J., Mar 2024, 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024. Beyersdorff, O., Kante, M. M., Kupferman, O. & Lokshtanov, D. (eds.). Dagstuhl, 52. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 289).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
    1 Citation (Scopus)
    93 Downloads (Pure)
  • 2023

    Approximation Ineffectiveness of a Tour-Untangling Heuristic

    Manthey, B. & van Rhijn, J., 22 Dec 2023, Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings. Byrka, J. & Wiese, A. (eds.). Cham: Springer, p. 1-13 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 14297 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
    55 Downloads (Pure)
  • 2020

    Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics

    Klootwijk, S. & Manthey, B., 10 Jun 2020, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Drmota, M. & Heuberger, C. (eds.). Dagstuhl: Dagstuhl, 16 p. 19. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 159).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
    51 Downloads (Pure)
  • 2019

    Probabilistic Analysis of Facility Location on Random Shortest Path Metrics

    Klootwijk, S. & Manthey, B., 19 Jun 2019, Computing with Foresight and Industry: 15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019, Proceedings. Manea, F., Martin, B., Paulusma, D. & Primiero, G. (eds.). Springer, p. 37-49 13 p. (Lecture Notes in Computer Science; vol. 11558).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    4 Downloads (Pure)

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

    Klootwijk, S., Manthey, B. & Visser, S. K., 1 Jan 2019, WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27-March 2, 2019. Proceedings. Nakano, S.-I., Das, G. K., Mandal, P. S. & Mukhopadhyaya, K. (eds.). Cham: Springer, p. 108-120 13 p. (Lecture Notes in Computer Science; vol. 11355)(Theoretical Computer Science and General Issues).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    2 Citations (Scopus)
    9 Downloads (Pure)
  • 2018

    Probabilistic Properties of Highly Connected Random Geometric Graphs

    Manthey, B. & Reijnders, V. M. J. J., 2018, Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings: 4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018, Proceedings. Panda, B. S. & Goswami, P. P. (eds.). Springer, p. 59-72 14 p. (Communications in Computer and Information Science; vol. 10743 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
    224 Downloads (Pure)
  • 2016

    Approximation Algorithms for k-Connected Graph Factors

    Manthey, B. & Waanders, M., 2016, Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA 2015). Sanita, L. & Skutella, M. (eds.). London: Springer, p. 1-12 12 p. (Lecture Notes in Computer Science; vol. 9499).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    1 Citation (Scopus)
    10 Downloads (Pure)
  • 2015

    Smoothed Analysis of Local Search Algorithms

    Manthey, B., 5 Aug 2015, Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015). Dehne, F., Sack, J.-R. & Stege, U. (eds.). London: Springer, p. 518-527 10 p. (Lecture Notes in Computer Science; vol. 9214).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

    1 Citation (Scopus)
    11 Downloads (Pure)

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

    Cornelissen, K. & Manthey, B., 4 Aug 2015, Proceedings of the 21st Computing and Combinatorics Conference (COCOON 2015). Xu, D., Du, D. & Du, D. (eds.). Berlin: Springer, p. 701-712 12 p. (Lecture Notes in Computer Science; vol. 9198).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    1 Citation (Scopus)
    2 Downloads (Pure)

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

    Cornelissen, K. & Manthey, B., 26 May 2015, Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Alkaya, A. F. & Duman, E. (eds.). Istanbul: Ozyegin Universitesi and Marmara Universitesi, p. 157-160 4 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    File
    145 Downloads (Pure)

  • Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP

    Künnemann, M. & Manthey, B., 26 May 2015, Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Alkaya, A. F. & Duman, E. (eds.). Istanbul, Turkey: Özyegin Üniversitesi and Marmara Üniversitesi, p. 1-4 4 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    File
    192 Downloads (Pure)

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

    Künnemann, M. & Manthey, B., 20 Jun 2015, Automata, Languages, and Programming: 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015). Halldorsson, M. M., Iwama, K., Kobayashi, N. & Speckmann, B. (eds.). Berlin: Springer, p. 859-871 13 p. (Lecture Notes in Computer Science; vol. 9134).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    8 Citations (Scopus)
    13 Downloads (Pure)
  • 2014

    Approximability of Connected Factors

    Cornelissen, K., Hoeksma, R. P., Manthey, B., Narayanaswamy, N. S. & Rahul, C. S., 2014, Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA 2013). Kaklamanis, C. & Pruhs, K. (eds.). Berlin, Germany: Springer, p. 120-131 12 p. (Lecture Notes in Computer Science; vol. 8447).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    6 Citations (Scopus)
    1 Downloads (Pure)

  • Decomposition algorithm for the single machine scheduling polytope

    Hoeksma, R. P., Manthey, B. & Uetz, M. J., 5 Mar 2014, Combinatorial Optimization, Third International Symposium, ISCO 2014. Springer, p. 280-291 12 p. (Lecture Notes in Computer Science; vol. 8596).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    File
    3 Citations (Scopus)
    205 Downloads (Pure)

  • Probabilistic analysis of power assignments

    de Graaf, M. & Manthey, B., 2014, 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014). Berlin: Springer, p. 201-212 12 p. (Lecture Notes in Computer Science; vol. 8635).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    4 Citations (Scopus)
    2 Downloads (Pure)
  • 2013

    Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2013) - Preface

    Hurink, J. L. & Manthey, B., 2013, Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Cornelissen, K., Hoeksma, R., Hurink, J. L. & Manthey, B. (eds.). Enschede: Centre for Telematics and Information Technology (CTIT), 1 p. (CTIT Workshop Proceedings; vol. WP 13-01).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

    File
    410 Downloads (Pure)

  • Random shortest paths: non-euclidean instances for metric optimization problems

    Bringmann, K., Engels, C., Manthey, B. & Rao, B. V. R., 2013, Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013). Chatterjee, K. & Sgall, J. (eds.). Berlin: Springer, p. 219-230 12 p. (Lecture Notes in Computer Science; vol. 8087).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    1 Citation (Scopus)
    3 Downloads (Pure)

  • Smoothed analysis of belief propagation for minimum-cost flow and matching

    Brunsch, T., Cornelissen, K., Manthey, B. & Röglin, H., 2013, Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013). Kumar Ghosh, S. & Tokuyama, T. (eds.). Berlin, Germany: Springer, p. 182-193 12 p. (Lecture Notes in Computer Science; vol. 7748).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    6 Citations (Scopus)
    1 Downloads (Pure)

  • Smoothed analysis of the 2-opt heuristic for the TSP: polynomial bounds for Gaussian noise

    Manthey, B. & Veenstra, R., 2013, Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013). Cai, L., Cheng, S.-W. & Lam, T.-W. (eds.). Berlin: Springer, p. 579-589 11 p. (Lecture Notes in Computer Science; vol. 8283).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    File
    17 Citations (Scopus)
    89 Downloads (Pure)

  • Smoothed analysis of the successive shortest path algorithm

    Brunsch, T., Cornelissen, K., Manthey, B. & Röglin, H., 2013, Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms. Khanna, S. (ed.). New Orleans, LA, USA: SIAM, p. 1180-1189 10 p. (Proceedings ACM-SIAM Symposium on Discrete Algorithms; vol. 2013, no. 24).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
    7 Citations (Scopus)
    17 Downloads (Pure)
  • 2012

    Random shortest path metrics with applications

    Engels, C., Manthey, B. & Raghavendra Rao, B. V., 2012, Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012). Brieden, A., Görgülü, Z.-K., Krug, T., Kropat, E., Meyer-Nieberg, S., Mihelcic, G. & Pickl, S. W. (eds.). Munich: Universität der Bundeswehr München, p. 121-124 4 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

    8 Downloads (Pure)

  • Smoothed complexity theory

    Bläser, M. & Manthey, B., 2012, 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012. Rovan, B., Sassone, V. & Widmayer, P. (eds.). New York: Springer, p. 198-209 12 p. (Lecture Notes in Computer Science; vol. 7464).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    3 Citations (Scopus)
    1 Downloads (Pure)
  • 2011

    Deterministic algorithms for multi-criteria TSP

    Manthey, B., 2011, Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011). Ogihara, M. & Tarui, J. (eds.). London: Springer, p. 264-275 12 p. (Lecture Notes in Computer Science; vol. 6648).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    3 Citations (Scopus)
    10 Downloads (Pure)

  • Smoothed analysis of partitioning algorithms for Euclidean functionals

    Bläser, M., Manthey, B. & Rao, B. V. R., 2011, 12th International Symposium on Algorithms and Data Structures, WADS 2011. Dehne, F., Iacono, J. & Sack, J.-R. (eds.). Berlin: Springer, p. 110-121 12 p. (Lecture Notes in Computer Science; vol. 6844).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    3 Citations (Scopus)
    9 Downloads (Pure)

  • Stochastic mean payoff games: smoothed analysis and approximation schemes

    Boros, E., Elbassioni, K., Fouz, M., Gurvich, V., Makino, K. & Manthey, B., 2011, Automata, Languages and Programming: 38th International Colloquium on Automata, Languages and Programming, ICALP 2011. Aceto, L., Henzinger, M. & Sgall, J. (eds.). Berlin: Springer, p. 147-158 12 p. (Lecture Notes in Computer Science; vol. 6755).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    16 Citations (Scopus)
    10 Downloads (Pure)
  • 2010

    Approximating independent set in semi-random graphs

    Manthey, B. & Plociennik, K., 2010, Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010). Faigle, U., Schrader, R. & Herrmann, D. (eds.). Cologne, Germany: University of Cologne, p. 119-122 4 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

    File
    89 Downloads (Pure)

  • Bisimplicial edges in bipartite graphs

    Bomhoff, M. J. & Manthey, B., 2010, Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010). Faigle, U., Schrader, R. & Herrmann, D. (eds.). Cologne, Germany: University of Cologne, p. 29-32 4 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

    File
    171 Downloads (Pure)

  • Multi-criteria TSP: Min and Max combined

    Manthey, B., 2010, 7th International Workshop Approximation and Online Algorithms (WAOA 2009). Bampis, E. & Jansen, K. (eds.). Berlin: Springer, p. 205-216 12 p. (Lecture Notes in Computer Science; vol. 5893).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    5 Citations (Scopus)
    4 Downloads (Pure)
  • 2009

    Improved smoothed analysis of the k-means method

    Manthey, B. & Röglin, H., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009. Mathieu, C. (ed.). Philadelphia: SIAM, p. 461-470 10 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    File
    20 Citations (Scopus)
    54 Downloads (Pure)

  • k-Means has polynomial smoothed complexity

    Arthur, D., Manthey, B. & Röglin, H., 2009, Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009). Spielman, D. A. (ed.). Los Alamitos, CA: IEEE, p. 405-414 10 p. (Annual IEEE Symposium on Foundations of Computer Science; vol. 2009, no. 50).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
    81 Citations (Scopus)
    292 Downloads (Pure)

  • On approximating multi-criteria TSP

    Manthey, B., 2009, Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009. Albers, S. & Marion, J.-Y. (eds.). Dagstuhl, p. 637-648 12 p. (LIPIcs–Leibniz International Proceedings in Informatics).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    Open Access
    File
    9 Citations (Scopus)
    104 Downloads (Pure)

  • On smoothed analysis of quicksort and Hoare's find

    Fouz, M., Kufleitner, M., Manthey, B. & Zeini Jahromi, N., 2009, Proceedings of the 15th Annual International Computing and Combinatorics Conference, COCOON 2009. Ngo, H. Q. (ed.). Berlin: Springer, p. 158-167 10 p. 10.1007/978-3-642-02882-3_17. (Lecture Notes in Computer Science; vol. 5609).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    2 Citations (Scopus)
    1 Downloads (Pure)

  • Worst-case and smoothed analysis of $k$-means clustering with Bregman divergences

    Manthey, B. & Röglin, H., 2009, Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC 2009. Dong, Y., Du, D. & Ibarra, O. (eds.). Berlin: Springer, p. 1024-1033 10 p. (Lecture Notes in Computer Science; vol. 5878).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    12 Citations (Scopus)
    3 Downloads (Pure)
  • 2008

    Approximating multi-criteria Max-TSP

    Bläser, M., Manthey, B. & Putz, O., 24 Dec 2008, Algorithms - ESA 2008: 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings. Halperin, D. & Mehlhorn, K. (eds.). Springer, p. 185-197 13 p. (Lecture Notes in Computer Science; vol. 5193).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    8 Citations (Scopus)

  • Smoothed analysis of binary search trees and quicksort under additive noise

    Manthey, B. & Tantau, T., 27 Oct 2008, Mathematical Foundations of Computer Science 2008 : 33rd International Symposium, MFCS 2008, Toru'n, Poland, August 25-29, 2008. Proceedings. Ochmański, E. & Tyszkiewicz, J. (eds.). Springer, p. 467-478 12 p. (Lecture Notes in Computer Science; vol. 5162).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    4 Citations (Scopus)
    1 Downloads (Pure)
  • 2007

    Approximation algorithms for multi-criteria traveling salesman problems

    Manthey, B. & Ram, L. S., 1 Dec 2007, Approximation and Online Algorithms: 4th International Workshop, WAOA 2006, Revised Papers. Erlebach, T. & Kaklamanis, C. (eds.). Berlin, Heidelberg: Springer, p. 302-315 14 p. (Lecture Notes in Computer Science; vol. 4368).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    2 Citations (Scopus)

  • Minimum-weight cycle covers and their approximability

    Manthey, B., 1 Dec 2007, Graph-Theoretic Concepts in Computer Science: 33rd International Workshop, WG 2007, Revised Papers. Springer, p. 178-189 12 p. (Lecture Notes in Computer Science; vol. 4769).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    1 Citation (Scopus)
  • 2006

    Approximability of minimum AND-circuits

    Arpe, J. & Manthey, B., 1 Jan 2006, Algorithm Theory – SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006: Proceedings. Arge, L. & Freivalds, R. (eds.). Springer, p. 292-303 12 p. (Lecture Notes in Computer Science; vol. 4059).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  • Approximation algorithms for restricted cycle covers based on cycle decompositions

    Manthey, B., 1 Jan 2006, Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006 Revised Papers. Fomin, F. V. (ed.). Berlin, Heidelberg: Springer, p. 336-347 12 p. (Lecture Notes in Computer Science; vol. 4271).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  • On approximating restricted cycle covers

    Manthey, B., 10 Jul 2006, Approximation and Online Algorithms: Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers. Erlebach, T. & Persinao, G. (eds.). Berlin, Heidelberg: Springer, p. 282-295 14 p. (Lecture Notes in Computer Science; vol. 3879).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    2 Citations (Scopus)
  • 2003

    Budget balanced mechanisms for the multicast pricing problem with rates

    Bläser, M. & Manthey, B., 2003, EC '03: Proceedings of the 4th ACM Conference on Electronic Commerce. New York, NY: Association for Computing Machinery, p. 194-195 2 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    1 Citation (Scopus)
  • 2002

    Improved approximation algorithms for Max-2SAT with cardinality constraint

    Bläser, M. & Manthey, B., 1 Dec 2002, Algorithms and Computation: 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21–23, 2002 Proceedings. Berlin, Heidelberg: Springer, p. 187-198 12 p. (Lecture Notes in Computer Science; vol. 2518).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    9 Citations (Scopus)

  • Two approximation algorithms for 3-cycle covers

    Bläser, M. & Manthey, B., 1 Jan 2002, Approximation Algorithms for Combinatorial Optimization: 5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings. Leonardi, S., Jansen, K. & Vazirani, V. (eds.). Berlin, Heidelberg: Springer, p. 40-50 11 p. (Lecture Notes in Computer Science; vol. 2462).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

    13 Citations (Scopus)