Mahya Jamshidian

dblp:313/0006 · DBLP profile ↗
← Back
3ranked-venue papers
0as first author
3since 2021 · last 2026
0009-0005-9937-0208ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 since 2021
YearPublicationVenuePosition
2026 Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
Zachary Friggstad, Mahya Jamshidian
Algorithmica2
2025 A Constant-Factor Approximation for Pairwise Fair k-Center Clustering
Sayan Bandyapadhyay, Tianzhi Chen, Zachary Friggstad, Mahya Jamshidian
IPCO4
2022 Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters
abstract
We give an improved approximation algorithm for two related clustering problems. In the Minimum Sum of Radii clustering problem (MSR), we are to select k balls in a metric space to cover all points while minimizing the sum of the radii of these balls. In the Minimum Sum of Diameters clustering problem (MSD), we are to simply partition the points of a metric space into k parts while minimizing the sum of the diameters of these parts. We present a 3.389-approximation for MSR and a 6.546-approximation for MSD, improving over their respective 3.504 and 7.008 approximations developed by Charikar and Panigrahy (2001). In particular, our guarantee for MSD is better than twice our guarantee for MSR. Our approach refines a so-called bipoint rounding procedure of Charikar and Panigrahy’s algorithm by considering centering balls at some points that were not necessarily centers in the bipoint solution. This added versatility enables the analysis of our improved approximation guarantees. We also provide an alternative approach to finding the bipoint solution using a straightforward LP rounding procedure rather than a primal-dual algorithm.
Zachary Friggstad, Mahya Jamshidian
ESA2