Cheap and Secure Web Hosting Provider : See Now

Array covering problem

, , No Comments
Problem Detail: 

Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \{ y_1, ..., y_M \}$. Let's define distance between sets $X$ and $Y$ to be $$d(X,Y) = \max_{i=1,...,N} ~~ \min_{k=1,...,M} ~ |x_i - y_k|$$

I would like to make $d(X,Y)$ minimum possible. Which algorithm should i use for choosing points $y_1, ..., y_M$ ?

Thanks in advance.

P.S. The original problem is taken from here: http://www.e-olymp.com/en/problems/3208

Asked By : Igor
Answered By : Yuval Filmus

Your problem is known as the unweighted one-dimensional $k$-center problem. See for example a recent paper by Chen, Li and Wang.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54428

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback