Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median

DOI10.1007/978-3-662-47672-7_10zbMath1418.68238OpenAlexW935408413MaRDI QIDQ3448778

Mohammad R. Salavatipour, Babak Behsaz, Rohit Sivakumar, Zachary Friggstad

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

Mathematics Subject Classification ID

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

Related Items (1)

Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs

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