<p>Consider any fixed location <span class="math-container">$j$</span>.  For any given center <span class="math-container">$i$</span>, let <span class="math-container">$X_{ij}$</span> be the fraction of demand from location <span class="math-container">$j$</span> assigned to <span class="math-container">$i$</span>.  Let <span class="math-container">$d_{ij}$</span> be the distance from location <span class="math-container">$j$</span> to <span class="math-container">$i$</span>.</p>
<p>The LP has a constraint <span class="math-container">$\sum_i X_{ij} = 1$</span>.  Consider the random experiment where <span class="math-container">$j$</span> chooses a single random center <span class="math-container">$i_j$</span> from the corresponding probability distribution (so <span class="math-container">$\Pr[i_j = i] = X_{ij}$</span> for all <span class="math-container">$i$</span>).</p>
<p>The expected cost of the random center is <span class="math-container">$\mu_j = \sum_i d_{ij} X_{ij}$</span>, which equals the corresponding contribution to the cost of the LP solution.</p>
<p>By a Markov bound, the probability that that cost exceeds <span class="math-container">$2\mu_j$</span> is at most 1/2.  So, if you look at the centers that are within distance <span class="math-container">$2\mu_j$</span> from <span class="math-container">$j$</span>, at least half of the weight of <span class="math-container">$j$</span>'s assignment goes to those centers.  This is the intuition.</p>
<p>So, for example, you can obtain a fractional solution <span class="math-container">$X'$</span> from <span class="math-container">$X$</span> by restricting each <span class="math-container">$j$</span> to be assigned to only the centers that are within distance <span class="math-container">$2\mu_j$</span> from <span class="math-container">$j$</span>, 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 &quot;open&quot;.)  This solution <span class="math-container">$X'$</span> will have opening cost at most twice that of <span class="math-container">$X$</span>'s opening cost, and will have assignment cost at most that of <span class="math-container">$X$</span>'s assignment cost, and furthermore <span class="math-container">$X'$</span> will assign each location <span class="math-container">$j$</span> only to centers that are at distance at most <span class="math-container">$2\mu_j$</span> from <span class="math-container">$j$</span>.</p>
<p>More generally by the same argument for any constant <span class="math-container">$\epsilon&gt;0$</span> you can get an <span class="math-container">$X'$</span> that has opening cost <span class="math-container">$O(1/\epsilon)$</span> times the opening cost of <span class="math-container">$X$</span>, and assigns each location <span class="math-container">$j$</span> only to centers that are at distance at most <span class="math-container">$(1+\epsilon)\mu_j$</span> from <span class="math-container">$j$</span>.</p>

CC BY-SA 4.0
2023-03-01T06:30:46.470Z
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?
ErroR
CC BY-SA 4.0
2023-03-01T06:41:57.157Z
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.
ErroR
CC BY-SA 4.0
2023-03-01T14:32:12.770Z
(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.
Neal Young
CC BY-SA 4.0
2023-02-27T15:35:28.903Z
2023-02-27T15:35:28.903Z
Neal Young
<p>I read <a href="https://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=&amp;cad=rja&amp;uact=8&amp;ved=2ahUKEwjli6T437X9AhWJOuwKHQ61DsIQFnoECAgQAQ&amp;url=http%3A%2F%2Ftheory.stanford.edu%2F%7Emoses%2Fpapers%2Fkmedian.ps&amp;usg=AOvVaw3Arv1bz2WXg3JSNGdHMn-L" rel="nofollow noreferrer">a paper</a> from Tardos et al. about <span class="math-container">$k-$</span>medians in metric space problem:
Given <span class="math-container">$N$</span> as set of points in metric space with distance function <span class="math-container">$c_{ij}$</span> for each <span class="math-container">$i,j\in N$</span>, demand <span class="math-container">$d_i$</span> for each point <span class="math-container">$i$</span> and integer <span class="math-container">$k$</span>. The goal is to find a set <span class="math-container">$T\subset N$</span> such that <span class="math-container">$|T|=k$</span> also   minimize <span class="math-container">$\sum_{i,j\in N}d_i\rho(i,j)$</span> where <span class="math-container">$\rho(i,j) $</span> is the distance of point <span class="math-container">$i$</span> to nearest center.</p>
<p>The paper use LP rounding technique to find a constant approximation factor for the problem.</p>
<p>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:</p>
<blockquote>
<p>Each location <span class="math-container">$j$</span>  has at least half of its  demand assigned  to
relatively  nearby partially open centers.</p>
</blockquote>
<p>My problem is are there any simple interpretation of above sentence or why that can help us?</p>

CC BY-SA 4.0
2023-02-27T15:36:11.677Z
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.
Neal Young
<ds.algorithms><approximation-algorithms><clustering>
$k-$median problem and filtering technique Lin and Vitter
ErroR
# $k-$median problem and filtering technique Lin and Vitter

(Asked by: username_0 on 2023-02-27)

I read [a paper](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwjli6T437X9AhWJOuwKHQ61DsIQFnoECAgQAQ&url=http%3A%2F%2Ftheory.stanford.edu%2F%7Emoses%2Fpapers%2Fkmedian.ps&usg=AOvVaw3Arv1bz2WXg3JSNGdHMn-L) 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?

**Tags:** ds.algorithms, approximation-algorithms, clustering
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2023-02-27. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: 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?  
> **username_0**: 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.  
> **username_1**: (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.  

---

