<p>We have <span class="math-container">$n$</span> customers, <span class="math-container">$(x_1, \dots, x_n)$</span>, sorted on the read line. For convenience, we also use <span class="math-container">$x_i$</span> to denote its coordinate on the line. We need to locate <span class="math-container">$m$</span> facilities on the real line. <strong>We note that these facilities can be located anywhere on the real line</strong>. Each facility <span class="math-container">$j\in [m]$</span> is associated with an entrance fee <span class="math-container">$f_j$</span>, such as the ticket money for a swimming pool. Given a location profile <span class="math-container">$(y_1, \dots, y_m)\in \mathcal{R}^m$</span> for the facilities(<span class="math-container">$(y_1, \dots, y_m)$</span> is not necessarily ordered), the cost for customer <span class="math-container">$i$</span> at facility <span class="math-container">$j$</span> is <span class="math-container">$c_{ij} = |x_i- y_j|+f_j$</span>, which can be understood as the aggregate money of the travelling cost and the entrance fee when you taxi to a swimming pool and purchase a ticket to swim inside. And the customer will always choose the facility so as to minimize her cost.</p>
<p>Our goal is to find a location profile <span class="math-container">$(y_1, \dots, y_m)$</span> for the given <span class="math-container">$m$</span> facilities such that the total minimum cost</p>
<p><span class="math-container">$$\sum_{i\in [n]}\min_{j\in [m]}c_{ij}$$</span>
is minimized.</p>
<p><strong>An easy but critical obserbation is that there is an optimal solution where each facility is located in the median agent of the continuous region of agents it serves</strong>. If we have identical entrance fees, we only need to find the optimal <span class="math-container">$m$</span> continuous partitions, which can be solved by dynamic programming in <span class="math-container">$O(mn^2)$</span>. For the general case, similar DP algortihm runs in <span class="math-container">$O(2^mn^2)$</span>. The algorithm, however, is exponential in <span class="math-container">$m$</span> and only makes sense after we've proved the problem is NP-hard. Another observation which may be helpful is that for if we have known the optimal <span class="math-container">$m$</span> continuous partitions, we just assign the facility of the <span class="math-container">$k$</span>-th smallest entrance fee to the partition of the <span class="math-container">$k$</span>-th most customers.</p>
<p>So is this problem NP-hard?  Or is there an algorithm running in polynomial time?</p>
<p><strong>Update</strong></p>
<p>Below is the detailed DP algorithms for the special case where all entrance fees are identical and the general case:</p>
<ol>
<li><p>For the spcial case, denote by <span class="math-container">$M(i,j,k)$</span> the minimum total cost when customer <span class="math-container">$i$</span> is in the <span class="math-container">$k$</span>-th partition and customer <span class="math-container">$j$</span> the right boundary of this partition. Depending on whether or not customer <span class="math-container">$i-1$</span> is still in the <span class="math-container">$k$</span>-partition, we derive the following transition function:
<span class="math-container">$$M(i,j,k)=  \min\{M(i-1,j,k), M(i-1,i-1,k-1)+c(i,j)\}$$</span>
where <span class="math-container">$c(i,j)$</span> is the minimum total cost of partition <span class="math-container">$[i,j]$</span>, i.e., total cost for these customers when exact one facility is located in the median of <span class="math-container">$[i,j]$</span>.</p>
<p>Obvious, this DP runs in <span class="math-container">$O(mn^2)$</span>.</p>
</li>
<li><p>For the general case, <strong>the key difference is that we have to decide which facility is located in the rightmost partition since now facilities are heterogeneous</strong>. Similarly we denote by <span class="math-container">$M(i,j,F)$</span> the minimum total cost when customer <span class="math-container">$i$</span> is in the rightmost partiton, customer <span class="math-container">$j$</span> is the right boundary of this partition and <span class="math-container">$F$</span> is the set of facilities to be located. Similarly again, we can derive the following transition function:
<span class="math-container">$$M(i,j,F)=  \min\{M(i-1,j,F), \\ \min_{s\in F}\{M(i-1,i-1,F\setminus\{s\})+c^{\prime}(i,j,f_s)\}\}$$</span>
where <span class="math-container">$c^{\prime}(i,j,f_s)$</span> is the total cost of <span class="math-container">$[i,j]$</span> when a facility with entrance fee <span class="math-container">$f_s$</span> is locate in the median of <span class="math-container">$[i,j]$</span>.</p>
<p>This DP runs in <span class="math-container">$O(2^mn^2)$</span></p>
</li>
</ol>

CC BY-SA 4.0
2021-01-03T01:00:01.560Z
I don't think your formulation is as you intended. In your formulation there's a separate cost $f_j$ for every client i connected to facility j (since $f_j$ is a part of $c_{ij}$). 

Assuming that I read that correctly, I think there should exist a simple DP along the number line. The only relevant state at every DP point is the rightmost open facility to the left of the current DP point (and the minimum cost achieved this way for all clients located to the left of that facility).
Magnus Wahlström
CC BY-SA 4.0
2021-01-05T03:38:56.307Z
@MagnusWahlström I didn't completely get how your DP works. The exponential part of my DP lies in the fact that we have to decide which facility is located in the rightmost partition. Do you think your DP could bypass this difficulty? And I've updated the details of my DP algorithms for your information, please have a look when you have time. Thanks a lot!
asdfqwer
CC BY-SA 4.0
2021-01-05T10:10:03.930Z
Actually, I misread the instructions. Apologies.
Magnus Wahlström
CC BY-SA 4.0
2021-01-05T11:18:52.223Z
@MagnusWahlström That's all right. Now I tend to think the problem is NP-hard. But I could barely find an appropriate base NP-hard problem for the reduction, being stuck for three weeks :)
asdfqwer
CC BY-SA 4.0
2021-02-24T06:27:35.180Z
Cross-posted: https://cs.stackexchange.com/q/133555/755, https://cstheory.stackexchange.com/q/48066/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<ds.algorithms><np-hardness><cg.comp-geom><polynomial-time>
NP-hardness for one-dimensional facility location problem with entrance fee for each customer
asdfqwer
# NP-hardness for one-dimensional facility location problem with entrance fee for each customer

(Asked by: username_0 on 2020-12-20)

We have $n$ customers, $(x\_1, \dots, x\_n)$, sorted on the read line. For convenience, we also use $x\_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. **We note that these facilities can be located anywhere on the real line**. Each facility $j\in [m]$ is associated with an entrance fee $f\_j$, such as the ticket money for a swimming pool. Given a location profile $(y\_1, \dots, y\_m)\in \mathcal{R}^m$ for the facilities($(y\_1, \dots, y\_m)$ is not necessarily ordered), the cost for customer $i$ at facility $j$ is $c\_{ij} = |x\_i- y\_j|+f\_j$, which can be understood as the aggregate money of the travelling cost and the entrance fee when you taxi to a swimming pool and purchase a ticket to swim inside. And the customer will always choose the facility so as to minimize her cost.

Our goal is to find a location profile $(y\_1, \dots, y\_m)$ for the given $m$ facilities such that the total minimum cost

$$\sum\_{i\in [n]}\min\_{j\in [m]}c\_{ij}$$
is minimized.

**An easy but critical obserbation is that there is an optimal solution where each facility is located in the median agent of the continuous region of agents it serves**. If we have identical entrance fees, we only need to find the optimal $m$ continuous partitions, which can be solved by dynamic programming in $O(mn^2)$. For the general case, similar DP algortihm runs in $O(2^mn^2)$. The algorithm, however, is exponential in $m$ and only makes sense after we've proved the problem is NP-hard. Another observation which may be helpful is that for if we have known the optimal $m$ continuous partitions, we just assign the facility of the $k$-th smallest entrance fee to the partition of the $k$-th most customers.

So is this problem NP-hard? Or is there an algorithm running in polynomial time?

**Update**

Below is the detailed DP algorithms for the special case where all entrance fees are identical and the general case:

1. For the spcial case, denote by $M(i,j,k)$ the minimum total cost when customer $i$ is in the $k$-th partition and customer $j$ the right boundary of this partition. Depending on whether or not customer $i-1$ is still in the $k$-partition, we derive the following transition function:
   $$M(i,j,k)= \min\{M(i-1,j,k), M(i-1,i-1,k-1)+c(i,j)\}$$
   where $c(i,j)$ is the minimum total cost of partition $[i,j]$, i.e., total cost for these customers when exact one facility is located in the median of $[i,j]$.

   Obvious, this DP runs in $O(mn^2)$.
2. For the general case, **the key difference is that we have to decide which facility is located in the rightmost partition since now facilities are heterogeneous**. Similarly we denote by $M(i,j,F)$ the minimum total cost when customer $i$ is in the rightmost partiton, customer $j$ is the right boundary of this partition and $F$ is the set of facilities to be located. Similarly again, we can derive the following transition function:
   $$M(i,j,F)= \min\{M(i-1,j,F), \\ \min\_{s\in F}\{M(i-1,i-1,F\setminus\{s\})+c^{\prime}(i,j,f\_s)\}\}$$
   where $c^{\prime}(i,j,f\_s)$ is the total cost of $[i,j]$ when a facility with entrance fee $f\_s$ is locate in the median of $[i,j]$.

   This DP runs in $O(2^mn^2)$

**Tags:** ds.algorithms, np-hardness, cg.comp-geom, polynomial-time
> **Comments:**
> **username_1**: I don't think your formulation is as you intended. In your formulation there's a separate cost $f_j$ for every client i connected to facility j (since $f_j$ is a part of $c_{ij}$).   Assuming that I read that correctly, I think there should exist a simple DP along the number line. The only relevant state at every DP point is the rightmost open facility to the left of the current DP point (and the minimum cost achieved this way for all clients located to the left of that facility).  
> **username_0**: @MagnusWahlström I didn't completely get how your DP works. The exponential part of my DP lies in the fact that we have to decide which facility is located in the rightmost partition. Do you think your DP could bypass this difficulty? And I've updated the details of my DP algorithms for your information, please have a look when you have time. Thanks a lot!  
> **username_1**: Actually, I misread the instructions. Apologies.  
> **username_0**: @MagnusWahlström That's all right. Now I tend to think the problem is NP-hard. But I could barely find an appropriate base NP-hard problem for the reduction, being stuck for three weeks :)  
> **username_2**: Cross-posted: https://cs.stackexchange.com/q/133555/755, https://cstheory.stackexchange.com/q/48066/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 0 answers

