<p>For the non-metric <span class="math-container">$k$</span>-median problem, we can show a stronger inapproximability result than <span class="math-container">$O(\log n)$</span>. The following is a stronger claim:</p>
<p><strong>Main Claim</strong>: The non-metric <span class="math-container">$k$</span>-median problem can not be approximated to any factor better than <span class="math-container">$n^{c}$</span>, for any constant <span class="math-container">$c&gt;0$</span>.</p>
<p><strong>Proof:</strong></p>
<p>The proof follows from the reduction from the hardness of the <em>max <span class="math-container">$k$</span> coverag</em>e problem. Given a universe set <span class="math-container">$U = \{1,\dotsc,n\}$</span> and subsets <span class="math-container">$S_{1}, \dotsc,S_{m}$</span> of <span class="math-container">$U$</span>. It is NP-hard to distinguish between the following instances:</p>
<ol>
<li><p>Yes Instances: There are some <span class="math-container">$k$</span> sets <span class="math-container">$S_{t_{1}},\dotsc,S_{t_{k}}$</span> that covers all elements in <span class="math-container">$U$</span>.</p>
</li>
<li><p>No Instances: There does not exists any <span class="math-container">$k$</span> sets in <span class="math-container">$S_{1}, \dotsc,S_{m}$</span> that can cover more than <span class="math-container">$(1-\frac{1}{e}) \cdot |U|$</span> elements of <span class="math-container">$U$</span>.</p>
</li>
</ol>
<blockquote>
<p><strong>Reduction:</strong> Using an instance of the max <span class="math-container">$k$</span> coverage, we construct a <span class="math-container">$k$</span>-median instance <span class="math-container">$(L,C)$</span> as follows. A location in <span class="math-container">$L$</span> corresponds to a subset <span class="math-container">$S_{i}$</span>. And, a client in
<span class="math-container">$C$</span> corresponds to an element <span class="math-container">$e_{j}$</span>. Let <span class="math-container">$f_{i} \in L$</span> denote a
location corresponding to <span class="math-container">$S_{i}$</span>, and <span class="math-container">$x_{j} \in C$</span> denote a client
corresponding to an element <span class="math-container">$e_{j} \in U$</span>. The distance between
<span class="math-container">$f_{i}$</span> and <span class="math-container">$x_{j}$</span> is <span class="math-container">$1$</span> if <span class="math-container">$e_{j} \in S_{i}$</span> and <span class="math-container">$\Delta$</span>
otherwise. Here <span class="math-container">$\Delta$</span> is some value <span class="math-container">$\gg 1$</span>.</p>
</blockquote>
<p>Now, let us compute the <span class="math-container">$k$</span>-median cost of <span class="math-container">$(L,C)$</span> corresponding to a <em>Yes Instance</em>.</p>
<p><em>Completeness:</em> We open facilities at the locations that corresponds to <span class="math-container">$S_{t_{1}}, \dotsc,S_{t_{k}}$</span>. The cost of every client to the closest facility would be exactly <span class="math-container">$1$</span> since every element belongs to some <span class="math-container">$S_{t_{i}}$</span>. Therefore, the <span class="math-container">$k$</span>-median cost is at most <span class="math-container">$|U|$</span>.</p>
<p>Now, let us compute the <span class="math-container">$k$</span>-median cost of <span class="math-container">$(L,C)$</span> corresponding to a <em>No Instance</em>.</p>
<p><em>Soundness:</em> No matter where we open <span class="math-container">$k$</span> facilities, there always exist at least <span class="math-container">$\frac{1}{e} \cdot |U|$</span> elements that are left uncovered. In other words, there are at least <span class="math-container">$\frac{1}{e} \cdot |U|$</span> clients at a distance of <span class="math-container">$\Delta$</span> from any open facility. Therefore, the <span class="math-container">$k$</span>-median cost is at least <span class="math-container">$\Delta \cdot \frac{1}{e} \cdot |U|$</span></p>
<p>The <em>completeness</em> and <em>soundness</em> analysis imply that the non-metric <span class="math-container">$k$</span>-median problem can not be approximated to any factor better than <span class="math-container">$\Delta \cdot \frac{1}{e}$</span>. Here, we can set <span class="math-container">$\Delta$</span> to any arbitrary large value <span class="math-container">$\gg n^{c}$</span> for any constant <span class="math-container">$c&gt;0$</span>. This completes the proof of the main claim.</p>
<hr />
<p>Note that I could not find the above result in any literature. However, the above reduction is similar to the one used by <a href="https://www.sciencedirect.com/science/article/abs/pii/S0196677498909932" rel="nofollow noreferrer">Guha and Khuller</a> where they take a distance of <span class="math-container">$1$</span> if <span class="math-container">$e_{j} \in S_{i}$</span> and <span class="math-container">$3$</span> otherwise. Using it they show the hardness of approximation for the metric facility location problem and other related problems.</p>

CC BY-SA 4.0
2021-02-22T11:23:59.410Z
Good answer. Interestingly, it looks to me like you don't even need here the hardness of approximation, as even one uncovered element would cost $\Delta$, which can be taken as some arbitrarily large $\mathrm{poly}(n)$ value. Two small typos: in the reduction paragraph, $\Delta$ is called a constant, and in the soundness, the number of uncovered elements should be at least $|U|/e$ instead of $(1-1/e)|U|$.
user3209423940248
CC BY-SA 4.0
2021-02-22T12:35:02.240Z
@user3209423940248 Thanks for verifying the answer and pointing out the correct errors. I have made the corrections.
Inuyasha Yagami
CC BY-SA 4.0
2021-02-22T12:35:57.583Z
@user3209423940248 Yes you are right. We do not even need the hardness of approximation here. Moreover, the reduction works for the k-means and k-center problems also.
Inuyasha Yagami
CC BY-SA 4.0
2021-02-22T10:03:36.370Z
2021-02-22T12:34:09.917Z
2021-02-22T12:34:09.917Z
Inuyasha Yagami
<p>It is well-known that the non-metric $k$-median problem cannot be approximated better than $O(\log(n))$ (by a gap preserving reduction from the set cover problem). Is there any logarithmic approximation algorithms for this problem? </p>

<p>In some real world applications, the cost function does not satisfies the triangle inequality even in a weak sense. Also, the constraint of not having more than $k$ medians cannot be violated and the above approximation ratio is the ratio of solution cost over optimal cost.</p>

CC BY-SA 3.0
2013-09-05T05:59:08.167Z
See Neal Young's answer here http://cstheory.stackexchange.com/questions/12329/facility-location-problem-with-a-cost-function
Austin Buchanan
CC BY-SA 3.0
2013-09-05T17:51:43.787Z
@AustinBuchanan I am looking for an approximation algorithm that does not open more than k medians. This constraint cannot be relaxed in the my application. If I do not miss anything, the algorithm cited by Neal Young opens $O(k\log(n))$ medians.
randomizer
CC BY-SA 3.0
2015-12-09T20:29:16.067Z
You can recast the approximation guarantees for existing algorithms to achieve at least some guarantee for opening $k$ facilities.  For example, one classical guarantee says that with $k H_n$ facilities, you can achieve assignment cost that is at most the optimal assignment cost achievable with $k$ facilities.  This is essentially the same as saying that, with $k$ facilities, you can achieve assignment cost that is at most the optimal assignment cost that can be achieved with $k/H_n$ facilities.
Neal Young
CC BY-SA 4.0
2021-02-22T16:43:47.967Z
Given any Set Cover instance, create a k-median instance in the standard way where customers are elements, sets are facilities, and the cost for a "set" to serve an "element" is zero if the set contains the element and 1 otherwise.  There is a set of k medians giving assignment cost zero iff there is a set cover of size k.  This reduction shows that you can't meet the budget of k while simultaneously achieving any cost bound (w.r.t. OPT) on the assignment cost.
Neal Young
CC BY-SA 4.0
2021-02-22T20:21:36.680Z
@NealYoung Your answer is indeed correct. But my answer is also correct. I do not understand why it got downvoted :-(
Inuyasha Yagami
CC BY-SA 4.0
2021-02-23T22:01:35.180Z
@InuyashaYagami, I'm not sure either.  I've just given it an upvote. :-)
Neal Young
<approximation-algorithms><approximation-hardness><clustering>
The non-metric k-median problem
randomizer
# The non-metric k-median problem

(Asked by: username_0 on 2013-09-05)

It is well-known that the non-metric $k$-median problem cannot be approximated better than $O(\log(n))$ (by a gap preserving reduction from the set cover problem). Is there any logarithmic approximation algorithms for this problem?

In some real world applications, the cost function does not satisfies the triangle inequality even in a weak sense. Also, the constraint of not having more than $k$ medians cannot be violated and the above approximation ratio is the ratio of solution cost over optimal cost.

**Tags:** approximation-algorithms, approximation-hardness, clustering

> **Comments:**
> **username_1**: See username_2's answer here http://cstheory.stackexchange.com/questions/12329/facility-location-problem-with-a-cost-function  
> **username_0**: @AustinBuchanan I am looking for an approximation algorithm that does not open more than k medians. This constraint cannot be relaxed in the my application. If I do not miss anything, the algorithm cited by username_2 opens $O(k\log(n))$ medians.  
> **username_2**: You can recast the approximation guarantees for existing algorithms to achieve at least some guarantee for opening $k$ facilities.  For example, one classical guarantee says that with $k H_n$ facilities, you can achieve assignment cost that is at most the optimal assignment cost achievable with $k$ facilities.  This is essentially the same as saying that, with $k$ facilities, you can achieve assignment cost that is at most the optimal assignment cost that can be achieved with $k/H_n$ facilities.  
> **username_2**: Given any Set Cover instance, create a k-median instance in the standard way where customers are elements, sets are facilities, and the cost for a "set" to serve an "element" is zero if the set contains the element and 1 otherwise.  There is a set of k medians giving assignment cost zero iff there is a set cover of size k.  This reduction shows that you can't meet the budget of k while simultaneously achieving any cost bound (w.r.t. OPT) on the assignment cost.  
> **username_3**: @NealYoung Your answer is indeed correct. But my answer is also correct. I do not understand why it got downvoted :-(  
> **username_2**: @InuyashaYagami, I'm not sure either.  I've just given it an upvote. :-)  

---

## 1 answers

### Answer by username_3 on 2021-02-22. Score: 1

For the non-metric $k$-median problem, we can show a stronger inapproximability result than $O(\log n)$. The following is a stronger claim:

**Main Claim**: The non-metric $k$-median problem can not be approximated to any factor better than $n^{c}$, for any constant $c>0$.

**Proof:**

The proof follows from the reduction from the hardness of the *max $k$ coverag*e problem. Given a universe set $U = \{1,\dotsc,n\}$ and subsets $S\_{1}, \dotsc,S\_{m}$ of $U$. It is NP-hard to distinguish between the following instances:

1. Yes Instances: There are some $k$ sets $S\_{t\_{1}},\dotsc,S\_{t\_{k}}$ that covers all elements in $U$.
2. No Instances: There does not exists any $k$ sets in $S\_{1}, \dotsc,S\_{m}$ that can cover more than $(1-\frac{1}{e}) \cdot |U|$ elements of $U$.

> **Reduction:** Using an instance of the max $k$ coverage, we construct a $k$-median instance $(L,C)$ as follows. A location in $L$ corresponds to a subset $S\_{i}$. And, a client in
> $C$ corresponds to an element $e\_{j}$. Let $f\_{i} \in L$ denote a
> location corresponding to $S\_{i}$, and $x\_{j} \in C$ denote a client
> corresponding to an element $e\_{j} \in U$. The distance between
> $f\_{i}$ and $x\_{j}$ is $1$ if $e\_{j} \in S\_{i}$ and $\Delta$
> otherwise. Here $\Delta$ is some value $\gg 1$.

Now, let us compute the $k$-median cost of $(L,C)$ corresponding to a *Yes Instance*.

*Completeness:* We open facilities at the locations that corresponds to $S\_{t\_{1}}, \dotsc,S\_{t\_{k}}$. The cost of every client to the closest facility would be exactly $1$ since every element belongs to some $S\_{t\_{i}}$. Therefore, the $k$-median cost is at most $|U|$.

Now, let us compute the $k$-median cost of $(L,C)$ corresponding to a *No Instance*.

*Soundness:* No matter where we open $k$ facilities, there always exist at least $\frac{1}{e} \cdot |U|$ elements that are left uncovered. In other words, there are at least $\frac{1}{e} \cdot |U|$ clients at a distance of $\Delta$ from any open facility. Therefore, the $k$-median cost is at least $\Delta \cdot \frac{1}{e} \cdot |U|$

The *completeness* and *soundness* analysis imply that the non-metric $k$-median problem can not be approximated to any factor better than $\Delta \cdot \frac{1}{e}$. Here, we can set $\Delta$ to any arbitrary large value $\gg n^{c}$ for any constant $c>0$. This completes the proof of the main claim.

---

Note that I could not find the above result in any literature. However, the above reduction is similar to the one used by [Guha and Khuller](https://www.sciencedirect.com/science/article/abs/pii/S0196677498909932) where they take a distance of $1$ if $e\_{j} \in S\_{i}$ and $3$ otherwise. Using it they show the hardness of approximation for the metric facility location problem and other related problems.

> **Comments:**
> **username_4**: Good answer. Interestingly, it looks to me like you don't even need here the hardness of approximation, as even one uncovered element would cost $\Delta$, which can be taken as some arbitrarily large $\mathrm{poly}(n)$ value. Two small typos: in the reduction paragraph, $\Delta$ is called a constant, and in the soundness, the number of uncovered elements should be at least $|U|/e$ instead of $(1-1/e)|U|$.  
> **username_3**: @username_4 Thanks for verifying the answer and pointing out the correct errors. I have made the corrections.  
> **username_3**: @username_4 Yes you are right. We do not even need the hardness of approximation here. Moreover, the reduction works for the k-means and k-center problems also.  

---

