A quantization framework for smoothed analysis of Euclidean optimization problems
From MaRDI portal
Publication:893320
DOI10.1007/S00453-015-0043-5zbMATH Open1342.90114OpenAlexW2241501243MaRDI QIDQ893320FDOQ893320
Authors: 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
Recommendations
- A quantization framework for smoothed analysis of Euclidean optimization problems
- Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- Typical Properties of Winners and Losers [0.2ex] in Discrete Optimization
- Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems
bin packingmaximum matchingsmoothed analysistravelling salesmanaverage case complexityEuclidean optimization problems
Cites Work
- Title not available (Why is that?)
- Bin packing can be solved within 1+epsilon in linear time
- Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
- Two Algorithmic Results for the Traveling Salesman Problem
- Title not available (Why is that?)
- The planar \(k\)-means problem is NP-hard
- Smoothed analysis of algorithms
- A polynomial algorithm for b-matchings: An alternative approach
- A survey of heuristics for the weighted matching problem
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- 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
- A PTAS for k-means clustering based on weak coresets
- Smoothed analysis of the \(k\)-means method
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
- A local search approximation algorithm for \(k\)-means clustering
- Center-based clustering under perturbation stability
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- The geometric maximum traveling salesman problem
- Partitioning heuristics for two geometric maximization problems
- Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems
- Typical Properties of Winners and Losers [0.2ex] in Discrete Optimization
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- A quantization framework for smoothed analysis of Euclidean optimization problems
- Euclidean matching problems and the metropolis algorithm
- Solving a "Hard" problem to approximate an "Easy" one
Cited In (4)
Uses Software
This page was built for publication: A quantization framework for smoothed analysis of Euclidean optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q893320)
