More Like this

1. Approximation Algorithms for Socially Fair Clustering

   Makarychev, Yury; Vakilian, Ali (January 2021, Proceedings of the Conference on Learning Theory, PMLR)

   Belkin, Mikhail; Kpotufe, Samor (Ed.)

   We present an $$e^{O(p)} (\log \ell) / (\log \log \ell)$$-approximation algorithm for socially fair clustering with the $$\ell_p$$-objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or several) of $$\ell$$ groups. The goal is to find a $$k$$-medians, $$k$$-means, or, more generally, $$\ell_p$$-clustering that is simultaneously good for all of the groups. More precisely, we need to find a set of $$k$$ centers $$C$$ so as to minimize the maximum over all groups $$j$$ of $$\sum_{u \text{ in group } j} d(u, C)^p$$. The socially fair clustering problem was independently proposed by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021). Our algorithm improves and generalizes their $$O(\ell)$$-approximation algorithms for the problem. The natural LP relaxation for the problem has an integrality gap of $$\Omega(\ell)$$. In order to obtain our result, we introduce a strengthened LP relaxation and show that it has an integrality gap of $$\Theta((\log \ell) / (\log \log \ell))$$ for a fixed p. Additionally, we present a bicriteria approximation algorithm, which generalizes the bicriteria approximation of Abbasi et al. (2021). 

   more » « less
2. Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error

   https://doi.org/10.1609/aaai.v36i6.20565  

   Chaturvedi, Anamay; Jones, Matthew; Nguyen, Huy L. (January 2022, Proceedings of the AAAI Conference on Artificial Intelligence)

   Given a data set of size n in d'-dimensional Euclidean space, the k-means problem asks for a set of k points (called centers) such that the sum of the l_2^2-distances between the data points and the set of centers is minimized. Previous work on this problem in the local differential privacy setting shows how to achieve multiplicative approximation factors arbitrarily close to optimal, but suffers high additive error. The additive error has also been seen to be an issue in implementations of differentially private k-means clustering algorithms in both the central and local settings. In this work, we introduce a new locally private k-means clustering algorithm that achieves near-optimal additive error whilst retaining constant multiplicative approximation factors and round complexity. Concretely, given any c>sqrt(2), our algorithm achieves O(k^(1 + O(1/(2c^2-1))) * sqrt(d' n) * log d' * poly log n) additive error with an O(c^2) multiplicative approximation factor. 

   more » « less
3. Clustering with faulty centers

   https://doi.org/10.1016/j.comgeo.2023.102052  

   Fox, Emily; Huang, Hongyao; Raichel, Benjamin (February 2024, Computational Geometry)

   In this paper we introduce and formally study the problem of $$k$$-clustering with faulty centers. Specifically, we study the faulty versions of $$k$$-center, $$k$$-median, and $$k$$-means clustering, where centers have some probability of not existing, as opposed to prior work where clients had some probability of not existing. For all three problems we provide fixed parameter tractable algorithms, in the parameters $$k$$, $$d$$, and $$\eps$$, that $$(1+\eps)$$-approximate the minimum expected cost solutions for points in $$d$$ dimensional Euclidean space. For Faulty $$k$$-center we additionally provide a 5-approximation for general metrics. Significantly, all of our algorithms have only a linear dependence on $$n$$. 

   more » « less
4. From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs

   https://doi.org/10.4230/LIPIcs.ESA.2024.42  

   Chekuri, Chandra; Jain, Rhea; Kulkarni, Shubhang; Zheng, Da Wei; Zhu, Weihao (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)

   In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph G = (V,E), a root vertex r and a set S ⊆ V of k terminals. The goal is to find a min-cost subgraph that connects r to each of the terminals. DST admits an O(log² k/log log k)-approximation in quasi-polynomial time [Grandoni et al., 2022; Rohan Ghuge and Viswanath Nagarajan, 2022], and an O(k^{ε})-approximation for any fixed ε > 0 in polynomial-time [Alexander Zelikovsky, 1997; Moses Charikar et al., 1999]. Resolving the existence of a polynomial-time poly-logarithmic approximation is a major open problem in approximation algorithms. In a recent work, Friggstad and Mousavi [Zachary Friggstad and Ramin Mousavi, 2023] obtained a simple and elegant polynomial-time O(log k)-approximation for DST in planar digraphs via Thorup’s shortest path separator theorem [Thorup, 2004]. We build on their work and obtain several new results on DST and related problems. - We develop a tree embedding technique for rooted problems in planar digraphs via an interpretation of the recursion in [Zachary Friggstad and Ramin Mousavi, 2023]. Using this we obtain polynomial-time poly-logarithmic approximations for Group Steiner Tree [Naveen Garg et al., 2000], Covering Steiner Tree [Goran Konjevod et al., 2002] and the Polymatroid Steiner Tree [Gruia Călinescu and Alexander Zelikovsky, 2005] problems in planar digraphs. All these problems are hard to approximate to within a factor of Ω(log² n/log log n) even in trees [Eran Halperin and Robert Krauthgamer, 2003; Grandoni et al., 2022]. - We prove that the natural cut-based LP relaxation for DST has an integrality gap of O(log² k) in planar digraphs. This is in contrast to general graphs where the integrality gap of this LP is known to be Ω(√k) [Leonid Zosin and Samir Khuller, 2002] and Ω(n^{δ}) for some fixed δ > 0 [Shi Li and Bundit Laekhanukit, 2022]. - We combine the preceding results with density based arguments to obtain poly-logarithmic approximations for the multi-rooted versions of the problems in planar digraphs. For DST our result improves the O(R + log k) approximation of [Zachary Friggstad and Ramin Mousavi, 2023] when R = ω(log² k). 

   more » « less
5. Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing

   https://doi.org/10.4230/LIPIcs.ESA.2024.41  

   Chekuri, Chandra; Jain, Rhea (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)

   We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [Chekuri et al., 2010; Guy Kortsarz and Zeev Nutov, 2011]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [Chekuri et al., 2010]. The rounding is based on recent results in hop-constrained oblivious routing [Ghaffari et al., 2021], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to h-hop constrained network design for which we obtain LP-based bicriteria approximation algorithms. We also consider a fault-tolerant version of h-hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k-1 edges can fail. This model has been considered in network design [Luis Gouveia and Markus Leitner, 2017; Gouveia et al., 2018; Arslan et al., 2020] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail. 

   more » « less