scientific article; zbMATH DE number 7378621

DOI10.4230/LIPICS.APPROX-RANDOM.2018.9MaRDI QIDQ5009501zbMATH OpenFDO

Authors Chandra Chekuri, Shalmoli Gupta

Publication date 4 August 2021

Full work available at URL https://arxiv.org/abs/1806.04202

zbMATH Keywords

beyond worst case analysisclusteringLP integralityoutliersperturbation resilience

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• \(k\)-center clustering under perturbation resilience
• \(k\)-center clustering under perturbation resilience
• Center-based clustering under perturbation stability
• Almost optimal solutions to k-clustering problems
• Partial recovery bounds for clustering with the relaxed K-means
• scientific article; zbMATH DE number 1247176
• On the complexity of clustering with relaxed size constraints in fixed dimension
• scientific article; zbMATH DE number 6902592

Cites work

• \(k\)-center clustering under perturbation resilience
• A Best Possible Heuristic for the k-Center Problem
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• Algorithms for facility location problems with outliers. (Extended abstract)
• Algorithms for stable and perturbation-resilient problems
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Approximate clustering without the approximation
• Approximation algorithms for clustering problems with lower bounds and outliers
• Are stable instances easy?
• Asymmetric k -center is log ^* n -hard to approximate
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Bilu-Linial stable instances of max cut and minimum multiway cut
• Center-based clustering under perturbation stability
• Clustering to minimize the maximum intercluster distance
• Constant approximation for k-median and k-means with outliers via iterative rounding
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 5764796 (Why is no real title available?)
• scientific article; zbMATH DE number 1757943 (Why is no real title available?)
• Improved spectral-norm bounds for clustering
• Least squares quantization in PCM
• On the practically interesting instances of MAXCUT
• Outlier analysis.
• The hardness of approximation of Euclidean k-means
• The non-uniform k-center problem

Cited in

(9)

• On perturbation resilience of non-uniform k-center
• \(k\)-center clustering under perturbation resilience
• \(k\)-center clustering under perturbation resilience
• Bilu-Linial stability, certified algorithms and the independent set problem
• Robust communication-optimal distributed clustering algorithms
• Robust \(k\)-center with two types of radii
• scientific article; zbMATH DE number 7758333 (Why is no real title available?)
• Clustering under perturbation stability in near-linear time
• Revisiting priority k-center: fairness and outliers

Describes a project that uses

Uses Software

• k-means++

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009501)