I read a paper from Tardos et al. about $k-$medians in metric space problem: Given $N$ as set of points in metric space with distance function $c_{ij}$ for each $i,j\in N$, demand $d_i$ for each point $i$ and integer $k$. The goal is to find a set $T\subset N$ such that $|T|=k$ also minimize $\sum_{i,j\in N}d_i\rho(i,j)$ where $\rho(i,j) $ is the distance of point $i$ to nearest center.

The paper use LP rounding technique to find a constant approximation factor for the problem.

I have a simple question as follow that I can't find intuition behind this theorem, the paper says that this come from Vitter and Line paper:

Each location $j$ has at least half of its demand assigned to relatively nearby partially open centers.

My problem is are there any simple interpretation of above sentence or why that can help us?

  • $\begingroup$ This is probably not a research-level question, so may be better suited to cs.se, and may be closed. Nonetheless I've given an answer below. $\endgroup$
    – Neal Young
    Feb 27, 2023 at 15:36

1 Answer 1


Consider any fixed location $j$. For any given center $i$, let $X_{ij}$ be the fraction of demand from location $j$ assigned to $i$. Let $d_{ij}$ be the distance from location $j$ to $i$.

The LP has a constraint $\sum_i X_{ij} = 1$. Consider the random experiment where $j$ chooses a single random center $i_j$ from the corresponding probability distribution (so $\Pr[i_j = i] = X_{ij}$ for all $i$).

The expected cost of the random center is $\mu_j = \sum_i d_{ij} X_{ij}$, which equals the corresponding contribution to the cost of the LP solution.

By a Markov bound, the probability that that cost exceeds $2\mu_j$ is at most 1/2. So, if you look at the centers that are within distance $2\mu_j$ from $j$, at least half of the weight of $j$'s assignment goes to those centers. This is the intuition.

So, for example, you can obtain a fractional solution $X'$ from $X$ by restricting each $j$ to be assigned to only the centers that are within distance $2\mu_j$ from $j$, doubling the amount assigned to each such center, and reducing the amount assigned to other centers to zero. (To make this feasible, also double the amount that each center is "open".) This solution $X'$ will have opening cost at most twice that of $X$'s opening cost, and will have assignment cost at most that of $X$'s assignment cost, and furthermore $X'$ will assign each location $j$ only to centers that are at distance at most $2\mu_j$ from $j$.

More generally by the same argument for any constant $\epsilon>0$ you can get an $X'$ that has opening cost $O(1/\epsilon)$ times the opening cost of $X$, and assigns each location $j$ only to centers that are at distance at most $(1+\epsilon)\mu_j$ from $j$.

  • $\begingroup$ Thank you for your great answer. I have a problem: "that cost" refers to $\mu_j$? Also, the main issue is, according to Markov bound, we find out the probability of our $\mu_j$ cost of LP exceeds from $2\mu$ is at most $\frac{1}{2}$. Merely, I can't understand how do we use the fact that at least half of the weight of $j$ goes to those centers? $\endgroup$
    – ErroR
    Mar 1, 2023 at 6:30
  • $\begingroup$ I consider $X_{ij}$ as the probability that, $j$ is assigned to center $i$. But you consider it as fraction demand that goes from $j$ to center $i$. I can't relate to these definitions. $\endgroup$
    – ErroR
    Mar 1, 2023 at 6:41
  • $\begingroup$ (i) "That cost" refers to "the cost of the random center", that is, $d_{i_j j}$. (ii) We can use it as described in the last two paragraphs of the answer. (iii) Yes, $X_{ij}$ is both of those things. I can't help you beyond that. $\endgroup$
    – Neal Young
    Mar 1, 2023 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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