2
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ See Neal Young's answer here cstheory.stackexchange.com/questions/12329/… $\endgroup$ Sep 5 '13 at 5:59
  • $\begingroup$ @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. $\endgroup$
    – Randomizer
    Sep 5 '13 at 17:51
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Dec 9 '15 at 20:29
  • 2
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Feb 22 at 16:43
  • 1
    $\begingroup$ @InuyashaYagami, I'm not sure either. I've just given it an upvote. :-) $\endgroup$
    – Neal Young
    Feb 23 at 22:01
1
$\begingroup$

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$ coverage 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 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.

$\endgroup$
3
  • 1
    $\begingroup$ 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|$. $\endgroup$ Feb 22 at 11:23
  • $\begingroup$ @user3209423940248 Thanks for verifying the answer and pointing out the correct errors. I have made the corrections. $\endgroup$ Feb 22 at 12:35
  • $\begingroup$ @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. $\endgroup$ Feb 22 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.