Bodo Manthey

According to our database1, Bodo Manthey authored at least 75 papers between 2001 and 2020.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics.
Proceedings of the 31st International Conference on Probabilistic, 2020

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
Probabilistic analysis of power assignments.
Random Struct. Algorithms, 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.
Discret. Appl. Math., 2016

Note on VCG vs. Price Raising for Matching Markets.
CoRR, 2016

2015
Smoothed Complexity Theory.
ACM Trans. Comput. Theory, 2015

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

12th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2013).
Discret. Appl. Math., 2015

Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems.
Algorithmica, 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

2014
Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372).
Dagstuhl Reports, 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

Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching.
J. Graph Algorithms Appl., 2013

Approximating independent set in perturbed graphs.
Discret. Appl. Math., 2013

Bisimplicial edges in bipartite graphs.
Discret. Appl. Math., 2013

Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.
Algorithmica, 2013

Approximability of Connected Factors.
Proceedings of the Approximation and Online Algorithms - 11th International Workshop, 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

Multi-criteria TSP: Min and max combined.
Oper. Res. Lett., 2012

Deterministic algorithms for multi-criteria Max-TSP.
Discret. Appl. Math., 2012

On Smoothed Analysis of Quicksort and Hoare's Find.
Algorithmica, 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 Inf. Technol., 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

2009
Average-case approximation ratio of the 2-opt algorithm for the TSP.
Oper. Res. Lett., 2009

Minimum-weight cycle covers and their approximability.
Discret. Appl. Math., 2009

Approximation Algorithms for Multi-Criteria Traveling Salesman Problems.
Algorithmica, 2009

Approximability of Minimum AND-Circuits.
Algorithmica, 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

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

Improved Smoothed Analysis of the k-Means Method
CoRR, 2008

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

2007
Smoothed analysis of binary search trees.
Theor. Comput. Sci., 2007

Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
Electronic Colloquium on Computational Complexity (ECCC), 2007

On Approximating Restricted Cycle Covers.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Approximate Pareto Curves for the Asymmetric Traveling Salesman Problem
CoRR, 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

2005
The intractability of computing the Hamming distance.
Theor. Comput. Sci., 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

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

Approximability of cycle covers and smoothed analysis of binary search trees.
PhD thesis, 2005

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

2003
Non-approximability of weighted multiple sequence alignment.
Theor. Comput. Sci., 2003

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

The Computational Power of Compiling C++.
Bull. 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

2002
Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint.
Proceedings of the Algorithms and Computation, 13th International Symposium, 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


  Loading...