Mahya Jamshidian

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.

Linear threshold models have long served to intuitively capture binary decision-makings in contexts such as vaccination, trading, and innovation, imposing "to take an action if enough fellows do so". Similarly, anti-threshold models have been used in contexts such as following fashion, volunteering, and routing, complying "to take an action if not too many fellows do so". Despite the achieved useful insights, these models are often against the common-sense intuition that human decision-making is a mixture of both: "to take an action if enough but not too many fellows do so". We capture this missing aspect of human perception and introduce the bi- threshold models, where each individual rather than one, has a pair of possibly unique thresholds and takes an action if and only if the number of others doing so is between the two thresholds. We find the equilibria of the resulting population dynamics and perform convergence analysis for homogeneous populations. Our analysis highlights the difference between bi- threshold and single-threshold models. In particular, we show that cooperation may be a rare outcome compared to single- threshold models. This highlights the dramatic difference in estimations of the cooperators using threshold models in critical situations such as taking vaccination in a pandemic.