EDBT 2026 Demo / reviewers in the wild / expert
Mahya Jamshidian
dblp:313/0006
· DBLP profile ↗
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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
Zachary Friggstad, Mahya Jamshidian |
Algorithmica | 2 |
| 2025 | A Constant-Factor Approximation for Pairwise Fair k-Center Clustering
Sayan Bandyapadhyay, Tianzhi Chen, Zachary Friggstad, Mahya Jamshidian |
IPCO | 4 |
| 2022 | Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or DiametersabstractWe 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 |
ESA | 2 |