Approximation Algorithms for Aversion k-Clustering via Local k-Median

DOI10.4230/LIPICS.ICALP.2016.66zbMATH Open1388.68308OpenAlexW2535784277MaRDI QIDQ4598205FDOQ4598205

Authors: Anupam Gupta, Guru Prashanth Guruganesh, Melanie Schmidt 

Publication date: 19 December 2017

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6218/pdf/LIPIcs-ICALP-2016-66.pdf/

Recommendations

• Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
• Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
• A local search approximation algorithm for \(k\)-means clustering
• A local search approximation algorithm for \(k\)-means clustering
• Polynomial-time approximation schemes for geometric min-sum median clustering
• Learning Theory
• Attainable accuracy guarantee for the \(k\)-medians clustering in [0, 1]
• scientific article; zbMATH DE number 2165699
• \(k\)-median clustering under discrete Fréchet and Hausdorff distances

zbMATH Keywords

clusteringapproximation algorithms\(k\)-medianprimal-dual method

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Cited In (5)

• Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
• Attainable accuracy guarantee for the \(k\)-medians clustering in [0, 1]
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• An improved approximation algorithm for squared metric \(k\)-facility location
• Connected \(k\)-center and \(k\)-diameter clustering

This page was built for publication: Approximation Algorithms for Aversion k-Clustering via Local k-Median

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