| Publication | Date of Publication | Type |
|---|
| Worst-case and smoothed analysis of the hartigan-Wong method for \(k\)-means clustering | 2025-11-10 | Paper |
| Approximation ineffectiveness of a tour-untangling heuristic | 2024-07-19 | Paper |
Probabilistic analysis of optimization problems on sparse random shortest path metrics
Algorithmica | 2023-12-13 | Paper |
| Approximation Ineffectiveness of a Tour-Untangling Heuristic | 2023-02-22 | Paper |
| Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics | 2023-02-07 | Paper |
| Improved Smoothed Analysis of 2-Opt for the Euclidean TSP | 2022-11-30 | Paper |
| Smoothed Analysis of Local Search | 2022-02-04 | Paper |
Probabilistic properties of highly connected random geometric graphs
Discrete Applied Mathematics | 2021-10-21 | Paper |
In memoriam Walter Kern
Discrete Applied Mathematics | 2021-09-15 | Paper |
Probabilistic analysis of optimization problems on generalized random shortest path metrics
Theoretical Computer Science | 2021-04-14 | Paper |
Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
Journal of Graph Algorithms and Applications | 2020-09-04 | Paper |
Probabilistic analysis of facility location on random shortest path metrics
(available as arXiv preprint) | 2020-05-12 | Paper |
Probabilistic analysis of optimization problems on generalized random shortest path metrics
Lecture Notes in Computer Science | 2019-10-15 | Paper |
Perturbation resilience for the facility location problem
Operations Research Letters | 2019-06-11 | Paper |
Smoothed analysis of the successive shortest path algorithm
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| Improved smoothed analysis of the \(k\)-means method | 2019-05-06 | Paper |
Approximating bounded-degree spanning trees and connected factors with leaves
Operations Research Letters | 2019-02-22 | Paper |
Approximation schemes for stochastic mean payoff games with perfect information and few random positions
Algorithmica | 2019-01-11 | Paper |
Belief propagation for the maximum-weight independent set and minimum spanning tree problems
Theoretical Computer Science | 2018-06-18 | Paper |
Probabilistic properties of highly connected random geometric graphs
Algorithms and Discrete Applied Mathematics | 2018-06-05 | Paper |
Approximation algorithms for connected graph factors of minimum weight
Theory of Computing Systems | 2018-04-12 | Paper |
Probabilistic analysis of power assignments
Random Structures & Algorithms | 2017-10-24 | Paper |
| Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences | 2017-03-09 | Paper |
Smoothed complexity theory
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope
Discrete Applied Mathematics | 2016-10-07 | Paper |
Approximation algorithms for \(k\)-connected graph factors
Approximation and Online Algorithms | 2016-02-26 | Paper |
Smoothed analysis of the successive shortest path algorithm
SIAM Journal on Computing | 2015-12-11 | Paper |
Smoothed analysis of local search algorithms
Lecture Notes in Computer Science | 2015-10-30 | Paper |
Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
Lecture Notes in Computer Science | 2015-10-29 | Paper |
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
Automata, Languages, and Programming | 2015-10-27 | Paper |
Decomposition algorithm for the single machine scheduling polytope
Lecture Notes in Computer Science | 2015-10-16 | Paper |
Random shortest paths: non-Euclidean instances for metric optimization problems
Algorithmica | 2015-09-03 | Paper |
Probabilistic analysis of power assignments
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
On approximating multicriteria \textsc{TSP}
ACM Transactions on Algorithms | 2014-09-09 | Paper |
Smoothed analysis of left-to-right maxima with applications
ACM Transactions on Algorithms | 2014-09-09 | Paper |
Approximability of connected factors
Approximation and Online Algorithms | 2014-09-02 | Paper |
k-Means Has Polynomial Smoothed Complexity
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Approximating independent set in perturbed graphs
Discrete Applied Mathematics | 2014-04-16 | Paper |
Bisimplicial edges in bipartite graphs
Discrete Applied Mathematics | 2014-04-16 | Paper |
Smoothed analysis of the \(k\)-means method
Journal of the ACM | 2014-02-17 | Paper |
Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
Algorithms and Computation | 2014-01-14 | Paper |
Smoothed analysis of belief propagation for minimum-cost flow and matching
Journal of Graph Algorithms and Applications | 2013-11-28 | Paper |
Random shortest paths: non-Euclidean instances for metric optimization problems
Lecture Notes in Computer Science | 2013-09-20 | Paper |
Smoothed analysis of partitioning algorithms for Euclidean functionals
Algorithmica | 2013-05-13 | Paper |
Smoothed analysis of belief propagation for minimum-cost flow and matching
WALCOM: Algorithms and Computation | 2013-04-12 | Paper |
Deterministic algorithms for multi-criteria max-TSP
Discrete Applied Mathematics | 2012-10-26 | Paper |
Smoothed complexity theory
Lecture Notes in Computer Science | 2012-09-25 | Paper |
Multi-criteria TSP: Min and Max combined
Operations Research Letters | 2012-07-06 | Paper |
On smoothed analysis of quicksort and Hoare's find
Algorithmica | 2012-04-26 | Paper |
| On approximating multi-criteria TSP | 2012-04-24 | Paper |
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
Lecture Notes in Computer Science | 2011-08-12 | Paper |
Stochastic mean payoff games: smoothed analysis and approximation schemes
Automata, Languages and Programming | 2011-07-06 | Paper |
Deterministic algorithms for multi-criteria TSP
Lecture Notes in Computer Science | 2011-07-01 | Paper |
Privacy in non-private environments
Theory of Computing Systems | 2011-04-01 | Paper |
Multi-criteria TSP: Min and Max combined
Approximation and Online Algorithms | 2010-05-11 | Paper |
Adding cardinality constraints to integer programs with applications to maximum satisfiability
Information Processing Letters | 2010-03-24 | Paper |
Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences
Algorithms and Computation | 2009-12-17 | Paper |
Non-approximability of weighted multiple sequence alignment for arbitrary metrics
Information Processing Letters | 2009-12-04 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2009-08-07 | Paper |
On Smoothed Analysis of Quicksort and Hoare’s Find
Lecture Notes in Computer Science | 2009-07-23 | Paper |
New lower and upper bounds for the competitive ratio of transmission protocols
Information Processing Letters | 2009-07-09 | Paper |
Minimum-weight cycle covers and their approximability
Discrete Applied Mathematics | 2009-06-30 | Paper |
Approximability of minimum AND-circuits
Algorithmica | 2009-06-17 | Paper |
Approximation algorithms for multi-criteria traveling salesman problems
Algorithmica | 2009-05-13 | Paper |
Average-case approximation ratio of the 2-opt algorithm for the TSP
Operations Research Letters | 2009-05-07 | Paper |
On Approximating Restricted Cycle Covers
SIAM Journal on Computing | 2009-03-16 | Paper |
Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
Lecture Notes in Computer Science | 2009-02-03 | Paper |
Approximating Multi-criteria Max-TSP
Algorithms - ESA 2008 | 2008-11-25 | Paper |
Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
Graph-Theoretic Concepts in Computer Science | 2008-09-04 | Paper |
Minimum-Weight Cycle Covers and Their Approximability
Graph-Theoretic Concepts in Computer Science | 2008-07-01 | Paper |
Approximation algorithms for multi-criteria traveling salesman problems
Lecture Notes in Computer Science | 2008-02-21 | Paper |
Approximability of Minimum AND-Circuits
Algorithm Theory – SWAT 2006 | 2007-09-07 | Paper |
Smoothed analysis of binary search trees
Theoretical Computer Science | 2007-07-09 | Paper |
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
Journal of Discrete Algorithms | 2007-02-14 | Paper |
Approximation and Online Algorithms
Lecture Notes in Computer Science | 2007-02-12 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2006-11-14 | Paper |
Private computation: \(k\)-connected versus 1-connected networks
Journal of Cryptology | 2006-11-03 | Paper |
| Privacy in Non-private Environments | 2005-08-12 | Paper |
Approximating maximum weight cycle covers in directed graphs with weights zero and one
Algorithmica | 2005-08-02 | Paper |
The intractability of computing the Hamming distance
Theoretical Computer Science | 2005-06-30 | Paper |
| scientific article; zbMATH DE number 1979498 (Why is no real title available?) | 2003-09-14 | Paper |
Non-approximability of weighted multiple sequence alignment.
Theoretical Computer Science | 2003-08-17 | Paper |
| scientific article; zbMATH DE number 1947046 (Why is no real title available?) | 2003-07-07 | Paper |
Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
(available as arXiv preprint) | N/A | Paper |
