Approximation algorithms for min-sum k-clustering and balanced k-median
From MaRDI portal
Publication:3448778
DOI10.1007/978-3-662-47672-7_10zbMATH Open1418.68238OpenAlexW935408413MaRDI QIDQ3448778FDOQ3448778
Authors: Babak Behsaz, Zachary Friggstad, Mohammad Salavatipour, R. Sivakumar 
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_10
Recommendations
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
- Approximating min-sum k -clustering in metric spaces
- A constant-factor approximation algorithm for the \(k\)-median problem
- Clustering for metric and nonmetric distance measures
- A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
Cites Work
- Approximating k-median via pseudo-approximation
- P-Complete Approximation Problems
- A tight bound on approximating arbitrary metrics by tree metrics
- Sublinear time algorithms for metric space problems
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
- Local Search Heuristics for k-Median and Facility Location Problems
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Approximation schemes for clustering problems
- Approximation algorithms for min-sum \(p\)-clustering
- Bypassing the embedding
- Approximating min-sum k -clustering in metric spaces
- Clustering for edge-cost minimization (extended abstract)
- Approximating \(k\)-median with non-uniform capacities
- Small Space Representations for Metric Min-Sum k-Clustering and Their Applications
Cited In (12)
- Small space representations for metric min-sum \(k\)-clustering and their applications
- On parameterized approximation algorithms for balanced clustering
- A constant-factor approximation algorithm for the \(k\)-median problem
- Faster balanced clusterings in high dimension
- Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs
- Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition
- Approximation Algorithms for Aversion k-Clustering via Local k-Median
- Squarepants in a tree, sum of subtree clustering and hyperbolic pants decomposition
- Approximation schemes for min-sum \(k\)-clustering
- Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem
- Approximation schemes for Min-Sum \(k\)-Clustering
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
This page was built for publication: Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448778)
