Tianzhi Chen

dblp:06/10174 · DBLP profile ↗
← Back
3ranked-venue papers
0as first author
3since 2021 · last 2025
0009-0005-5581-5834ORCID · reported

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

Theory of computation · 3 · 3 since 2021
YearPublicationVenuePosition
2025 Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints
abstract
In this work, we study k-min-sum-of-radii (k-MSR) clustering under mergeable constraints. k-MSR seeks to group data points using a set of up to k balls, such that the sum of the radii of the balls is minimized. A clustering constraint is called mergeable if merging two clusters satisfying the constraint, results in a cluster that also satisfies the constraint. Many popularly studied constraints are mergeable, including fairness constraints and lower bound constraints. In our work, we design a (4+ε)-approximation for k-MSR under any given mergeable constraint with runtime 2^{O(k/(ε)⋅log²k/ε)} n⁴, i.e., fixed-parameter tractable in k for constant ε. Our result directly improves upon the FPT (6+ε)-approximation by Carta et al. [Carta et al., 2024]. We also provide a hardness result that excludes the exact solvability of k-MSR under any given mergeable constraint in time f(k)n^o(k), assuming ETH is true.
Sayan Bandyapadhyay, Tianzhi Chen
APPROX/RANDOM2
2025 Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering
Sina Bagheri Nezhad, Sayan Bandyapadhyay, Tianzhi Chen
ESA3
2025 A Constant-Factor Approximation for Pairwise Fair k-Center Clustering
Sayan Bandyapadhyay, Tianzhi Chen, Zachary Friggstad, Mahya Jamshidian
IPCO2