Hardness of Approximation of Euclidean $k$-Median
- URL: http://arxiv.org/abs/2011.04221v1
- Date: Mon, 9 Nov 2020 06:50:34 GMT
- Title: Hardness of Approximation of Euclidean $k$-Median
- Authors: Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal
- Abstract summary: 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.
- Score: 0.25782420501870296
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Euclidean $k$-median problem is defined in the following manner: given a
set $\mathcal{X}$ of $n$ points in $\mathbb{R}^{d}$, and an integer $k$, find a
set $C \subset \mathbb{R}^{d}$ of $k$ points (called centers) such that the
cost function $\Phi(C,\mathcal{X}) \equiv \sum_{x \in \mathcal{X}} \min_{c \in
C} \|x-c\|_{2}$ is minimized. The Euclidean $k$-means problem is defined
similarly by replacing the distance with squared distance in the cost function.
Various hardness of approximation results are known for the Euclidean $k$-means
problem. However, no hardness of approximation results were known for the
Euclidean $k$-median problem. In this work, assuming the unique games
conjecture (UGC), we provide the first hardness of approximation result for the
Euclidean $k$-median problem.
Furthermore, we study the hardness of approximation for the Euclidean
$k$-means/$k$-median problems in the bi-criteria setting where an algorithm is
allowed to choose more than $k$ centers. That is, bi-criteria approximation
algorithms are allowed to output $\beta k$ centers (for constant $\beta>1$) and
the approximation ratio is computed with respect to the optimal
$k$-means/$k$-median cost. In this setting, we show the first hardness of
approximation result for the Euclidean $k$-median problem for any $\beta <
1.015$, assuming UGC. We also show a similar bi-criteria hardness of
approximation result for the Euclidean $k$-means problem with a stronger bound
of $\beta < 1.28$, again assuming UGC.
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) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
We study the problem of residual error estimation for matrix and vector norms using a linear sketch.
We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work.
We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
arXiv Detail & Related papers (2024-08-16T02:33:07Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al.
A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$.
We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
arXiv Detail & Related papers (2024-02-09T19:01:48Z) - 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) - Improved Coresets for Euclidean $k$-Means [24.850829728643923]
Given a set of $n$ points in $d$ dimensions, the Euclidean $k$-means problem (resp. the Euclidean $k$-median problem) consists of finding $k$ centers.
In this paper, we improve the upper bounds $tilde O(min(k2 cdot varepsilon-2,kcdot varepsilon-4)$ for $k$-means and $tilde O(min(k4/3 cdot varepsilon
arXiv Detail & Related papers (2022-11-15T14:47:24Z) - Bicriteria Approximation Algorithms for Priority Matroid Median [1.7188280334580193]
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.
arXiv Detail & Related papers (2022-10-04T20:19:55Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$.
We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
arXiv Detail & Related papers (2022-02-15T03:49:28Z) - Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization
Domain [11.562923882714093]
We study the problem of finding approximate first-order stationary points in optimization problems of the form $min_x in max_y in Y f(x,y)
Our approach relies upon replacing the function $f(x,cdot)$ with its $kth order Taylor approximation (in $y$) and finding a near-stationary point in $Y$.
arXiv Detail & Related papers (2021-10-08T07:46:18Z) - 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) - 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)
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.