Finding the k-center on real number line

Problem

Input: towns $t_1,t_2,...,t_n\in \mathbb{R}$ and $k$ is a number.

Output: find the $k$ stations $s_1,s_2,...,s_k\in \mathbb{R}$ such that we minimize the farthest town to the closest station, for any given $t_i$.

Intuitively, if we pick any $t_i$, we should not travel any further to get to a center $s_i$ than any other $t_j$.

Setup

Solution space: all the possible tuples $(s_1,s_2,...,s_k)\in {\mathbb{R}}^k$

Objective function $f$:

$$f(s_1,s_2,...,s_k)=\underset{i\in [\mathrm{1..}n]}{\max }\left\{\underset{j\in [\mathrm{1..}k]}{\min }\left\{|t_i-s_j|\right\}\right\}$$

This says that for each town $\mathrm{1..}n$, we pick the closest station among $\mathrm{1..}k$ and consider the distance between them. We want to minimize $f$ for all towns.

High-level question

We can ask “where to place the first station?” or (almost equivalently) “which towns should the first station serve?”

• Question is good because we decompose our problem: after placing the first station, we recurse and consider the remaining $k-1$ stations
• In addition, we consider the remaining set of towns that aren’t covered by a station yet
• The first phrasing of the question is not that good because it implies an infinite number of answers (because it’s a real number)

The possible answers are $i\in \mathrm{1..}n$, where $t_i$ signifies the last town that $s_1$ should cover. For each $i$, the payment of towns $t_1,...,t_i$ is given by

$$\text{max distance}=\frac{|t_1-t_i|}{2}$$

This is because we want to minimize the distance from the furthest town to station $s_1$. We have two towns on either end, so the median is the best.

$G$-function

The $G$-function in this problem is given by

$$G(\mathrm{1..}n,k)=\text{minimum }f\text{-value for servicing towns }{t}_1,\dots ,t_n\text{ using }k\text{-centers}$$

We don’t know how much the remaining towns will pay. If we choose to use the first station to cover up to town $t_i$, then

$$G(\mathrm{1..}n,k)=\underset{i\in [\mathrm{1..}n]}{\min }\left\{\max \left(\frac{|t_1-t_i|}{2},G(i+\mathrm{1..}n,k-1)\right)\right\}$$

Remember that the output only considers the maximum distance that any given town has to travel to its station, so we take the max of the first station, and however much the remaining towns have to pay for the remaining $k-1$ stations.

Generalization: “proof of correctness”

We can generalize $G$ for any station last town $i$ and number of stations $j$:

$$\begin{array}{rl}G(i,j)& =\text{min }f\text{-value of placing }j\text{ stations to serve towns }{t}_i,\dots ,t_n\\ & =\underset{l\in [i..n]}{\min }\left\{\max \left(\frac{t_i-t_l}{2},G(l+\mathrm{1..}n,j-1)\right)\right\}\end{array}$$

where $l$ is the last town covered by station $s_i$ from $t_i$ to $t_l$.

We have two base cases so that $G$ doesn’t infinitely recurse. Consider if we have no towns left. Then we would be recursing on town $n+1$, which doesn’t exist, so $G(n+1,j)=0$ for any $j$.

Furthermore, if we run out of stations, then $j=0$, in which case we’ve failed to cover all $n$ towns, and so this should not be considered. Then $G(i,0)=\infty$ for any town $i$.

Caching subproblems

We use a 2D array to store any previously calculated values for $(i,j)$ in $G$.

Runtime analysis

There are $n$ towns and $k$ problems, so there are $nk$ subproblems. For each subproblem, we need to recurse through $i..n$ towns to consider each as the last town for that particular station. When $i=1$, this is $n$ towns, so total runtime is given by

$$(\text{\# of subproblems})\cdot (\text{time per subproblem})=O(n^{2}k)$$