Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median

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

zbMATH Keywords

approximationdoubling metricsbalanced \(k\)-medianhierarchically separated treesmin-sum \(k\)-clustering

Mathematics Subject Classification ID

Dynamic programming (90C39) Approximation algorithms (68W25)

Related Items (2)

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

This page was built for publication: Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median