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?


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

  • $\begingroup$ Another observation is that, if the entrance fees are relatively small comparing with the travelling distance, then the optimal partition is the optimal partition in the case where all entrance fees are identical, which can be computed by a $O(mn^2)$ DP algorithm as you've mentioned. So maybe the partition given by the $O(mn^2)$ DP can serve as a base, and some adaptations or operations on it will lead to an optimal solution. $\endgroup$ – Mengfan Ma Dec 24 '20 at 6:27
  • $\begingroup$ fwiw, I suppose this can be solved by seeing it as 1-dimensional "k-means clustering" and using "naïve k-means" where the customers are the observations and the facilities are the centroids respectively. The distance of an observation to the centroid is defined as the cost of that customer to that facility and the new centroids are calculated by finding the optimal position of each facility in its cluster. $\endgroup$ – Albert Hendriks Dec 25 '20 at 19:40
  • $\begingroup$ @AlbertHendriks But the k-means clustering doesn't involve entrance fee as in my problem. $\endgroup$ – asdfqwer Dec 27 '20 at 9:15
  • $\begingroup$ Are $f_j$ rational numbers only? $\endgroup$ – MotiNK Dec 27 '20 at 18:13
  • $\begingroup$ @asdfqwer I know, but the entrance fees are included in the cost. The crux why it should work is that when you move a facility just a bit so that a certain customer now becomes "closer" (ie less cost) to a different facility, the cost for that customer increases only a bit. You just have to consider cost instead of distance in the algorithm. The observations do often not belong to the distance-closest centroids in our case, unlike the original k-means clustering algorithm, but it still works. The new centroids are calculated based on the observations that are closest to it wrt cost. $\endgroup$ – Albert Hendriks Dec 27 '20 at 20:56


The answer shows a reduction to the rainbow path problem and thus doesn't prove anything about the complexity of the given problem. See this paper which contains hardness results for related problems (theorem 2.3 states that rainbow s-t path is hard).

The problem is $\cancel{\text{still polynomial}}$, as it can still be reduced to some version of shortest path. Observe that there always exists an optimal solution where the facilities are a subset of $\{x_1,...,x_n\}$ (given an optimal solution and a facility $y_j$ in it, let $A_j$ denote the set of clients attending $y_j$, then replacing $y_j$ with the median of $A_j$ does not increase the value of the solution). Now construct a directed graph whose vertices are $V=\{s,t, v_{il}| i\in[n], l\in[m] \}$ and whose edges are given by:

$$E=\{(v_{il},v_{jk})| i<j\in[n], \text{and } l,k\in[m]\}\cup\{(s,v_{il})|i\in[n],l\in[m]\}\\\cup\{(v_{n,l},t) |l\in[m]\}$$

Interpret the edge $(v_{il},v_{jk})$ as choosing a solution where the clients $x_{i+1},...,x_j$ are members of the facility $y_k$. With this in mind, we set the weights of the edges to be:

$$ w(v_{il},v_{jk})=\sum\limits_{q=i+1}^j |x_q-m_{ij}|+(j-i)f_k\\ w(s,v_{il})=\sum\limits_{q=1}^i|x_q-m_{0,i}|+if_l\\ w(v_{n,l},t)=0, \text{ for all $l\in[m]$} $$

Where $m_{ij}$ is the median of $x_{i+1},...,x_j$. An optimal solution for your problem is the weight of the lightest path from $s$ to $t$ of length $\le m$ which uses at most one edge from the set $E_i=\left\{(v,v_{l,i})|v\in V, l\in [n]\right\}$ for every $i\in[m]$ (this implies that we do not use the same facility twice). This version of shortest (lightest) path can be solved in polynomial time (think of it as having $m$ different color edges, and we want a path that does not use the same color twice, I believe that a sort of modified Dijkstra should work).

  • 1
    $\begingroup$ Can you please elaborate on the last paragraph? I don't see how to do this and I think it's a crux of the problem. $\endgroup$ – user114966 Dec 23 '20 at 18:39
  • $\begingroup$ Also, I suspect that you actually can't do this. Intuition: the shortest path problem can be formulated as an LP problem, while the original problem can't (the feasible set is nonconvex). $\endgroup$ – user114966 Dec 23 '20 at 19:41
  • $\begingroup$ I suspect that you are right, It seemed easy at the time of writing. I'll leave this answer for now, perhaps someone would find this helpful. $\endgroup$ – Ariel Dec 23 '20 at 20:25
  • $\begingroup$ You've reduced the original problem to a special shortest path problem. The reduction is nice. But the problem is, can you solve this shortest path problem in polynomial time? It's not, at lease to me, very obvious. $\endgroup$ – Mengfan Ma Dec 24 '20 at 6:11
  • $\begingroup$ @Dmitry Could you please speak more about the intuition? $\endgroup$ – Mengfan Ma Dec 24 '20 at 6:13

This is not intended to be a full answer but rather to give a possible direction.

Assume $f_j$ are natural numbers. Then let $K = \sum_j f_j$.

Solve the following clustering problem for points $p_k$: $$ \arg\min_k \sum_i \min_k |x_i - p_k| $$

Then we need to assign each cluster a facility, such that facility $j$ is associated with $f_j$ clusters. Clearly, in order to minimize our objective these clusters need to be adjacent to each other.

Then, to determine facility $j$, we need to select the median point of clusters $c_j^1, c_j^2, \dots, c_j^{f_j}$.

Threats to validity: while $x_i$ may have belonged to a cluster, it is not guaranteed that it will be associated with the facility that that cluster is assigned to.

  • $\begingroup$ Are you solving a $K$-median problem for the given points in the first half of your answer? $\endgroup$ – asdfqwer Dec 30 '20 at 3:32
  • $\begingroup$ In principle, the smaller $f_i$ is, the more agents should be assigned to facility $i$. But I don't think the solution by your answer follows this principle. $\endgroup$ – asdfqwer Dec 30 '20 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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