The non-metric k-median problem

Question

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.

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