| 2025 | MFCS | Counting Locally Optimal Tours in the TSP. | Bodo Manthey, Jesse van Rhijn |
| 2025 | WG | Playing Snake on a Graph. | Denise Graafsma, Bodo Manthey, Alexander Skopalik |
| 2024 | ISAAC | Complexity of Local Search for Euclidean Clustering Problems. | Bodo Manthey, Nils Morawietz, Jesse van Rhijn, Frank Sommer |
| 2024 | STACS | Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering. | Bodo Manthey, Jesse van Rhijn |
| 2023 | ISAAC | Improved Smoothed Analysis of 2-Opt for the Euclidean TSP. | Bodo Manthey, Jesse van Rhijn |
| 2023 | WAOA | Approximation Ineffectiveness of a Tour-Untangling Heuristic. | Bodo Manthey, Jesse van Rhijn |
| 2020 | AofA | Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics. | Stefan Klootwijk, Bodo Manthey |
| 2019 | CiE | Probabilistic Analysis of Facility Location on Random Shortest Path Metrics. | Stefan Klootwijk, Bodo Manthey |
| 2019 | WALCOM | Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics. | Stefan Klootwijk, Bodo Manthey, Sander K. Visser |
| 2015 | COCOON | Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. | Kamiel Cornelissen, Bodo Manthey |
| 2015 | ICALP | Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic. | Marvin Knnemann, Bodo Manthey |
| 2015 | WADS | Smoothed Analysis of Local Search Algorithms. | Bodo Manthey |
| 2015 | WAOA | Approximation Algorithms for k-Connected Graph Factors. | Bodo Manthey, Marten Waanders |
| 2014 | MFCS | Probabilistic Analysis of Power Assignments. | Maurits de Graaf, Bodo Manthey |
| 2013 | ISAAC | Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise. | Bodo Manthey, Rianne Veenstra |
| 2013 | MFCS | Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems. | Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao |
| 2013 | SODA | Smoothed Analysis of the Successive Shortest Path Algorithm. | Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Rglin |
| 2013 | WALCOM | Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching. | Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Rglin |
| 2013 | WAOA | Approximability of Connected Factors. | Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul |
| 2012 | MFCS | Smoothed Complexity Theory. | Markus Blser, Bodo Manthey |
| 2011 | ICALP | Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes. | Endre Boros, Khaled M. Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey |
| 2011 | TAMC | Deterministic Algorithms for Multi-criteria TSP. | Bodo Manthey |
| 2011 | WADS | Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. | Markus Blser, Bodo Manthey, B. V. Raghavendra Rao |
| 2009 | COCOON | On Smoothed Analysis of Quicksort and Hoare's Find. | Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi |
| 2009 | FOCS | k-Means Has Polynomial Smoothed Complexity. | David Arthur, Bodo Manthey, Heiko Rglin |
| 2009 | ISAAC | Worst-Case and Smoothed Analysis of | Bodo Manthey, Heiko Rglin |
| 2009 | SODA | Improved smoothed analysis of the | Bodo Manthey, Heiko Rglin |
| 2009 | STACS | On Approximating Multi-Criteria TSP. | Bodo Manthey |
| 2009 | WAOA | Multi-Criteria TSP: Min and Max Combined. | Bodo Manthey |
| 2008 | ESA | Approximating Multi-criteria Max-TSP. | Markus Blser, Bodo Manthey, Oliver Putz |
| 2008 | MFCS | Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise. | Bodo Manthey, Till Tantau |
| 2007 | WG | Minimum-Weight Cycle Covers and Their Approximability. | Bodo Manthey |
| 2006 | WAOA | Approximation Algorithms for Multi-criteria Traveling Salesman Problems. | Bodo Manthey, L. Shankar Ram |
| 2006 | WG | Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions. | Bodo Manthey |
| 2005 | ISAAC | Smoothed Analysis of Binary Search Trees. | Bodo Manthey, Rdiger Reischuk |
| 2005 | WAOA | On Approximating Restricted Cycle Covers. | Bodo Manthey |
| 2004 | ASIACRYPT | Privacy in Non-private Environments. | Markus Blser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey |
| 2003 | ISAAC | The Intractability of Computing the Hamming Distance. | Bodo Manthey, Rdiger Reischuk |
| 2002 | ISAAC | Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint. | Markus Blser, Bodo Manthey |