$k-$median problem and filtering technique Lin and Vitter

Question

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?

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