A quantization framework for smoothed analysis of Euclidean optimization problems
From MaRDI portal
Publication:893320
DOI10.1007/s00453-015-0043-5zbMath1342.90114OpenAlexW2241501243MaRDI QIDQ893320
Radu Curticapean, Marvin Künnemann
Publication date: 19 November 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-0043-5
maximum matchingtravelling salesmanbin packingaverage case complexitysmoothed analysisEuclidean optimization problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The planar \(k\)-means problem is NP-hard
- A local search approximation algorithm for \(k\)-means clustering
- Center-based clustering under perturbation stability
- Partitioning heuristics for two geometric maximization problems
- A polynomial algorithm for b-matchings: An alternative approach
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- Bin packing can be solved within 1+epsilon in linear time
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems
- Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
- A survey of heuristics for the weighted matching problem
- The geometric maximum traveling salesman problem
- Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
- On coresets for k-means and k-median clustering
- Smoothed analysis of algorithms
- A PTAS for k-means clustering based on weak coresets
- Euclidean matching problems and the metropolis algorithm
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Two Algorithmic Results for the Traveling Salesman Problem
- Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
- Smoothed Analysis of the k-Means Method
- Solving a "Hard" problem to approximate an "Easy" one
- Typical Properties of Winners and Losers [0.2ex in Discrete Optimization]
