Bodo Manthey

According to our database1, Bodo Manthey authored at least 77 papers between 2001 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics.
Proceedings of the WALCOM: Algorithms and Computation - 13th International Conference, 2019

Probabilistic Analysis of Facility Location on Random Shortest Path Metrics.
Proceedings of the Computing with Foresight and Industry, 2019

2018
Belief propagation for the maximum-weight independent set and minimum spanning tree problems.
Theor. Comput. Sci., 2018

Perturbation resilience for the facility location problem.
Oper. Res. Lett., 2018

Approximation Algorithms for Connected Graph Factors of Minimum Weight.
Theory Comput. Syst., 2018

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

Probabilistic Properties of Highly Connected Random Geometric Graphs.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2018

2017
Approximating bounded-degree spanning trees and connected factors with leaves.
Oper. Res. Lett., 2017

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

2016
Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope.
Discrete Applied Mathematics, 2016

2015
Smoothed Analysis of the Successive Shortest Path Algorithm.
SIAM J. Comput., 2015

12th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2013).
Discrete Applied Mathematics, 2015

Approximation Algorithms for k-Connected Graph Factors.
Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

Smoothed Analysis of Local Search Algorithms.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

On the Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP.
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.
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.
Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

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

Probabilistic Analysis of Power Assignments.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Decomposition Algorithm for the Single Machine Scheduling Polytope.
Proceedings of the Combinatorial Optimization - Third International Symposium, 2014

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

Approximating independent set in perturbed graphs.
Discrete Applied Mathematics, 2013

Approximability of Connected Factors.
Proceedings of the Approximation and Online Algorithms - 11th International Workshop, 2013

Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching.
Proceedings of the WALCOM: Algorithms and Computation, 7th International Workshop, 2013

Smoothed Analysis of the Successive Shortest Path Algorithm.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems.
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.
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Smoothed analysis of the successive shortest path algorithm.
Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2013

2012
On approximating multicriteria TSP.
ACM Trans. Algorithms, 2012

Smoothed analysis of left-to-right maxima with applications.
ACM Trans. Algorithms, 2012

Deterministic algorithms for multi-criteria Max-TSP.
Discrete Applied Mathematics, 2012

Smoothed Complexity Theory.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Random Shortest Path Metrics with Applications.
Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2012

2011
Smoothed Analysis of the k-Means Method.
J. ACM, 2011

Smoothed Analysis: Analysis of Algorithms Beyond Worst Case.
it - Information Technology, 2011

Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Deterministic Algorithms for Multi-criteria TSP.
Proceedings of the Theory and Applications of Models of Computation, 2011

Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
Approximating Independent Set in Semi-Random Graphs.
Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2010

Bisimplicial Edges in Bipartite Graphs.
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.
Oper. Res. Lett., 2009

Multi-Criteria TSP: Min and Max Combined.
Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

On Approximating Multi-Criteria TSP.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Improved smoothed analysis of the k-means method.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

k-Means Has Polynomial Smoothed Complexity.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

On Smoothed Analysis of Quicksort and Hoare's Find.
Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

2008
Adding cardinality constraints to integer programs with applications to maximum satisfiability.
Inf. Process. Lett., 2008

Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

Approximating Multi-criteria Max-TSP.
Proceedings of the Algorithms, 2008

2007
Minimum-Weight Cycle Covers and Their Approximability.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2007

Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
Proceedings of the Probabilistic Methods in the Design and Analysis of Algorithms, 23.09., 2007

2006
Private Computation: k-Connected versus 1-Connected Networks.
J. Cryptology, 2006

An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality.
J. Discrete Algorithms, 2006

Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

Approximation Algorithms for Multi-criteria Traveling Salesman Problems.
Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

Approximability of Minimum AND-Circuits.
Proceedings of the Algorithm Theory, 2006

Approximability of Minimum AND-Circuits.
Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

2005
Non-approximability of weighted multiple sequence alignment for arbitrary metrics.
Inf. Process. Lett., 2005

Smoothed Analysis of the Height of Binary Search Trees
Electronic Colloquium on Computational Complexity (ECCC), 2005

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

On Approximating Restricted Cycle Covers.
Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

Smoothed Analysis of Binary Search Trees.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Approximability of cycle covers and smoothed analysis of binary search trees.
Proceedings of the Ausgezeichnete Informatikdissertationen 2005, 2005

2004
New lower and upper bounds for the competitive ratio of transmission protocols.
Inf. Process. Lett., 2004

Privacy in Non-private Environments.
Proceedings of the Advances in Cryptology, 2004

2003
Privacy in Non-Private Environments
Electronic Colloquium on Computational Complexity (ECCC), 2003

Private Computation - k-connected versus 1-connected Networks
Electronic Colloquium on Computational Complexity (ECCC), 2003

The Computational Power of Compiling C++.
Bulletin of the EATCS, 2003

Budget balanced mechanisms for the multicast pricing problem with rates.
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

The Intractability of Computing the Hamming Distance.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2002
Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

Private Computation - k-Connected versus 1-Connected Networks.
Proceedings of the Advances in Cryptology, 2002

Two Approximation Algorithms for 3-Cycle Covers.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001
Computing Cycle Covers without Short Cycles.
Proceedings of the Algorithms, 2001

Non-approximability of Weighted Multiple Sequence Alignment.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001


  Loading...