A quantization framework for smoothed analysis of Euclidean optimization problems

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

zbMATH Keywords

maximum matchingtravelling salesmanbin packingaverage case complexitysmoothed analysisEuclidean optimization problems

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27)

Uses Software

• k-means++

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]