Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
From MaRDI portal
Publication:666661
DOI10.1007/s00453-018-0454-1zbMath1418.68239OpenAlexW2803719094WikidataQ129811919 ScholiaQ129811919MaRDI QIDQ666661
Rohit Sivakumar, Babak Behsaz, Zachary Friggstad, Mohammad R. Salavatipour
Publication date: 11 March 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0454-1
approximationdoubling metricsbalanced \(k\)-medianhierarchically separated treesmin-sum \(k\)-clustering
Related Items
Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem ⋮ Approximation algorithms for fair \(k\)-median problem without fairness violation
Cites Work
- Unnamed Item
- Approximation algorithms for min-sum \(p\)-clustering
- Sublinear time algorithms for metric space problems
- Clustering for edge-cost minimization (extended abstract)
- Bypassing the embedding
- Approximation schemes for clustering problems
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- Small Space Representations for Metric Min-Sum k-Clustering and Their Applications
- P-Complete Approximation Problems
- Local Search Heuristics for k-Median and Facility Location Problems
- Approximating min-sum k -clustering in metric spaces
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Approximating k-median via pseudo-approximation
- A tight bound on approximating arbitrary metrics by tree metrics
