Bicriteria Approximation Algorithms for Priority Matroid Median
- URL: http://arxiv.org/abs/2210.01888v2
- Date: Thu, 6 Jul 2023 18:36:18 GMT
- Title: Bicriteria Approximation Algorithms for Priority Matroid Median
- Authors: Tanvi Bajpai and Chandra Chekuri
- Abstract summary: We consider the Priority Matroid Median problem which generalizes the Priority $k$-Median problem.
The goal is to choose a subset $S subseteq mathcalF$ of facilities to minimize the $sum_i in mathcalF f f_i.
- Score: 1.7188280334580193
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Fairness considerations have motivated new clustering problems and algorithms
in recent years. In this paper we consider the Priority Matroid Median problem
which generalizes the Priority $k$-Median problem that has recently been
studied. The input consists of a set of facilities $\mathcal{F}$ and a set of
clients $\mathcal{C}$ that lie in a metric space $(\mathcal{F} \cup
\mathcal{C},d)$, and a matroid $\mathcal{M}=(\mathcal{F},\mathcal{I})$ over the
facilities. In addition each client $j$ has a specified radius $r_j \ge 0$ and
each facility $i \in \mathcal{F}$ has an opening cost $f_i$. The goal is to
choose a subset $S \subseteq \mathcal{F}$ of facilities to minimize the
$\sum_{i \in \mathcal{F}} f_i + \sum_{j \in \mathcal{C}} d(j,S)$ subject to two
constraints: (i) $S$ is an independent set in $\mathcal{M}$ (that is $S \in
\mathcal{I}$) and (ii) for each client $j$, its distance to an open facility is
at most $r_j$ (that is, $d(j,S) \le r_j$). For this problem we describe the
first bicriteria $(c_1,c_2)$ approximations for fixed constants $c_1,c_2$: the
radius constraints of the clients are violated by at most a factor of $c_1$ and
the objective cost is at most $c_2$ times the optimum cost. We also improve the
previously known bicriteria approximation for the uniform radius setting ($r_j
:= L$ $\forall j \in \mathcal{C}$).
Related papers
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$.
As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
arXiv Detail & Related papers (2024-10-26T06:21:42Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization.
Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires.
We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
arXiv Detail & Related papers (2024-06-07T08:26:31Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model.
For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits.
For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
arXiv Detail & Related papers (2023-07-11T08:51:53Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem.
The goal is to approximate $mathbfA$ as a product of low-rank factors.
Our techniques generalize to other common variants of the BMF problem.
arXiv Detail & Related papers (2023-06-02T18:55:27Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
We show that even the special case of $k$-Center in dimension $Theta(log n)$ is $(sqrt3/2- o(1))$hard to approximate for FPT algorithms.
We also show that even the special case of $k$-Center in dimension $Theta(log n)$ is $(sqrt3/2- o(1))$hard to approximate for FPT algorithms.
arXiv Detail & Related papers (2023-05-12T08:43:28Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
arXiv Detail & Related papers (2021-09-06T14:21:43Z) - FPT Approximation for Socially Fair Clustering [0.38073142980733]
We are given a set of points $P$ in a metric space $mathcalX$ with a distance function $d(.,.)$.
The goal of the socially fair $k$-median problem is to find a set $C subseteq F$ of $k$ centers that minimizes the maximum average cost over all the groups.
In this work, we design $(5+varepsilon)$ and $(33 + varepsilon)$ approximation algorithms for the socially fair $k$-median and $k$-means
arXiv Detail & Related papers (2021-06-12T11:53:18Z) - Locally Private $k$-Means Clustering with Constant Multiplicative
Approximation and Near-Optimal Additive Error [10.632986841188]
We bridge the gap between the exponents of $n$ in the upper and lower bounds on the additive error with two new algorithms.
It is possible to solve the locally private $k$-means problem in a constant number of rounds with constant factor multiplicative approximation.
arXiv Detail & Related papers (2021-05-31T14:41:40Z) - Hardness of Approximation of Euclidean $k$-Median [0.25782420501870296]
The Euclidean $k$-median problem is defined in the following manner: given a set $mathcalX$ of $n$ points in $mathbbRd$, find a set $C subset mathbbRd$ of $k$ points (called centers)
In this work, we provide the first hardness of approximation result for the Euclidean $k$-median problem.
arXiv Detail & Related papers (2020-11-09T06:50:34Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized.
This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
arXiv Detail & Related papers (2020-04-16T19:16:38Z) - Sets Clustering [25.358415142404752]
We prove that a core-set of $O(logn)$ sets always exists, and can be computed in $O(nlogn)$ time.
Applying an inefficient but optimal algorithm on this coreset allows us to obtain the first PTAS ($1+varepsilon$ approximation) for the sets-$k$-means problem.
Open source code and experimental results for document classification and facility locations are also provided.
arXiv Detail & Related papers (2020-03-09T13:30:30Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.