<p>Let me post a solution (hopefully it's correct) based on the hint given by <a href="https://cstheory.stackexchange.com/users/176/chandra-chekuri">Chandra Chekuri</a> (comment above).</p>
<p><strong>A 3-approximation</strong></p>
<p>Let the optimal solution be <span class="math-container">$S^*$</span> then we can guess <span class="math-container">$\max_{i \in C} d(i, S^*)$</span> because there are at most <span class="math-container">$|F||C|$</span> possible numbers. Let's first assume that we know the correct guess, which is <span class="math-container">$R$</span>. We do the following:</p>
<blockquote class="spoiler">
<p> Pick a <span class="math-container">$c \in C$</span> and select the facility in <span class="math-container">$B(c, R)$</span> with the lowest opening cost. Call such a client &quot;considered.&quot;<br>
 Remove every client within <span class="math-container">$B(c, 2R)$</span>.<br>
 Repeat until there are no clients left.</p>
</blockquote>
<p><strong>Analysis</strong></p>
<blockquote class="spoiler">
<p> Let <span class="math-container">$S$</span> be the constructed facility set. We observe that by the triangle inequality, every client is at most <span class="math-container">$R+2R$</span> distance from <span class="math-container">$S$</span>. So our solution's radius satisfies <span class="math-container">$\max_{i \in C}d(i, S) \leq 3R=3 \max_{i \in C}d(i, S^*)$</span>.<br>
 Next we show that <span class="math-container">$\sum_{j \in S}f_j \leq \sum_{j \in S^*}f_j$</span>. Consider <span class="math-container">$B(c, R)$</span> for each <span class="math-container">$c \in C$</span> that is &quot;considered&quot; by our algorithm. Note that at least one facility in <span class="math-container">$S^*$</span> must be in each of these balls. By construction these balls are disjoint (since their centers are at least <span class="math-container">$2R$</span> away from each other but the radius is only <span class="math-container">$R$</span>), which means that the facilities opened by the optimal solution in these balls are distinct. Finally, since we always choose the lowest cost facility to open in these balls, the opening cost of our algorithm is not greater than that of the optimal algorithm.<br></p>
</blockquote>
<p>Finally, how do we do the guess? Of course in this problem the smallest <span class="math-container">$R$</span> possible might not be the radius of the optimal solution. But we can do the following:</p>
<blockquote class="spoiler">
<p> If the guessed <span class="math-container">$R$</span> does not allow a feasible construction (meaning some <span class="math-container">$B(c, R) \cap F = \varnothing$</span>), then we skip it as the optimal cannot have this radius.<br>
 For other guesses which we can make a construction on, we pick the solution with the smallest target function (not the radius). Note that least one guess is correct and for that guess the target function is a 3-approximation, then so is the construction with the smallest target function.</p>
</blockquote>

CC BY-SA 4.0
2024-10-23T04:49:26.063Z
2024-10-23T04:49:26.063Z
strategyproof
<p>I'm thinking about a variant of the facility location problem. Given a set of cities <span class="math-container">$C$</span> and facilities <span class="math-container">$F$</span>, we want to open a subset <span class="math-container">$S \subseteq F$</span> of facilities such that the following is minimized:</p>
<p><span class="math-container">$$
\max_{i \in C} d(i, S) + \sum_{j \in S} f_j,
$$</span></p>
<p>where <span class="math-container">$f_1, \dotsc, f_m$</span> are the opening costs of facilities and <span class="math-container">$d(\cdot, \cdot)$</span> is a metric.</p>
<p>The difference is that the first term is replaced by the objective function similar to that in the <span class="math-container">$k$</span>-center problem. Is there a known constant approximation to this problem?</p>

CC BY-SA 4.0
2024-10-22T12:03:57.493Z
Yes, there is. It follows relative easily from the standard k-center algorithm. First guess the optimal radius $\max_i d(i, S^*)$ and then use the $k$-center algorithm.
Chandra Chekuri
CC BY-SA 4.0
2024-10-22T22:08:40.973Z
Ignoring the costs of opening, by guessing and running $k$-center on the facilities we can get a 3-approximation. But how can we take the costs into consideration? I'm thinking about always selecting the min-cost facility but the algo could have deleted low cost facilities during the process.
strategyproof
CC BY-SA 4.0
2024-10-23T01:26:34.750Z
See Knapsack Center which is a cost-version of k-center.
Chandra Chekuri
CC BY-SA 4.0
2024-10-23T03:59:10.363Z
Oh thanks! I've figured it out now. Need to select the facilities and throw away the clients more carefully.
strategyproof
CC BY-SA 4.0
2024-10-23T12:08:24.970Z
Btw, it is not natural to combine constraints such as radius and facility costs. They are two different aspects of the problem are not on the same scale. This is just a comment from the modeling aspect. It is more natural to model one as a constraint and the other as an objective like what k-center does.
Chandra Chekuri
CC BY-SA 4.0
2024-10-23T14:01:09.637Z
Yes I agree. Turns out the algorithms can be the same though
strategyproof
<approximation-algorithms><clustering>
Approximation of a variant of facility location problem
strategyproof
# Approximation of a variant of facility location problem

(Asked by: username_0 on 2024-10-22)

I'm thinking about a variant of the facility location problem. Given a set of cities $C$ and facilities $F$, we want to open a subset $S \subseteq F$ of facilities such that the following is minimized:

$$
\max\_{i \in C} d(i, S) + \sum\_{j \in S} f\_j,
$$

where $f\_1, \dotsc, f\_m$ are the opening costs of facilities and $d(\cdot, \cdot)$ is a metric.

The difference is that the first term is replaced by the objective function similar to that in the $k$-center problem. Is there a known constant approximation to this problem?

**Tags:** approximation-algorithms, clustering
> **Comments:**
> **username_1**: Yes, there is. It follows relative easily from the standard k-center algorithm. First guess the optimal radius $\max_i d(i, S^*)$ and then use the $k$-center algorithm.  
> **username_0**: Ignoring the costs of opening, by guessing and running $k$-center on the facilities we can get a 3-approximation. But how can we take the costs into consideration? I'm thinking about always selecting the min-cost facility but the algo could have deleted low cost facilities during the process.  
> **username_1**: See Knapsack Center which is a cost-version of k-center.  
> **username_0**: Oh thanks! I've figured it out now. Need to select the facilities and throw away the clients more carefully.  
> **username_1**: Btw, it is not natural to combine constraints such as radius and facility costs. They are two different aspects of the problem are not on the same scale. This is just a comment from the modeling aspect. It is more natural to model one as a constraint and the other as an objective like what k-center does.  
> **username_0**: Yes I agree. Turns out the algorithms can be the same though  

---

## 1 answers

### Answer by username_0 on 2024-10-23. Score: 1 | Accepted answer

Let me post a solution (hopefully it's correct) based on the hint given by [Chandra Chekuri](https://cstheory.stackexchange.com/users/176/chandra-chekuri) (comment above).

**A 3-approximation**

Let the optimal solution be $S^\*$ then we can guess $\max\_{i \in C} d(i, S^\*)$ because there are at most $|F||C|$ possible numbers. Let's first assume that we know the correct guess, which is $R$. We do the following:

> Pick a $c \in C$ and select the facility in $B(c, R)$ with the lowest opening cost. Call such a client "considered."  
> Remove every client within $B(c, 2R)$.  
> Repeat until there are no clients left.

**Analysis**

> Let $S$ be the constructed facility set. We observe that by the triangle inequality, every client is at most $R+2R$ distance from $S$. So our solution's radius satisfies $\max\_{i \in C}d(i, S) \leq 3R=3 \max\_{i \in C}d(i, S^\*)$.  
> Next we show that $\sum\_{j \in S}f\_j \leq \sum\_{j \in S^\*}f\_j$. Consider $B(c, R)$ for each $c \in C$ that is "considered" by our algorithm. Note that at least one facility in $S^\*$ must be in each of these balls. By construction these balls are disjoint (since their centers are at least $2R$ away from each other but the radius is only $R$), which means that the facilities opened by the optimal solution in these balls are distinct. Finally, since we always choose the lowest cost facility to open in these balls, the opening cost of our algorithm is not greater than that of the optimal algorithm.

Finally, how do we do the guess? Of course in this problem the smallest $R$ possible might not be the radius of the optimal solution. But we can do the following:

> If the guessed $R$ does not allow a feasible construction (meaning some $B(c, R) \cap F = \varnothing$), then we skip it as the optimal cannot have this radius.  
> For other guesses which we can make a construction on, we pick the solution with the smallest target function (not the radius). Note that least one guess is correct and for that guess the target function is a 3-approximation, then so is the construction with the smallest target function.


---

