/prog/ CHALLENGE 2011

Given a set V of N 2 dimensional points and a number k (0 < k < N) find k circles which have the same radius r and the centers in V and cover all the N points in V and r must be the smallest possible.

An equivalent formulation of the problem would be given a point x and a finite set of points S we have dist(x, S) = min{dist(x,y) | y ∈ S} and radius(S) = max{dist(x, S) | x ∈ V}. You must determine a subset S ⊆ V, |S| = k which minimizes radius(S).

Binary search on R.
After that you can do some exponential DP or some shit, hell if I know.  I'm fairly sure the problem of determining whether you can solve this with a fixed R is not equivalent to the vertex cover problem, though.

In particular, I was thinking of the graph G=(V,E) where V=V from the problem statement and E={(v1,v2) in VxV | dist(v1,v2)<=R}.  If you look for a k-vertex cover on this graph you will get the wrong answer for the following input:
V = {(0,0),(1,0),(2,0),(3,0),(4,0),(5,0)} K=2.
The right answer is R=1 with circles at (1,0) and (4,0), but if we think about the problem as a quest for a k-vertex cover we'll fail because the edge ((2,0),(3,0)) won't be incident on either of our chosen vertices.

If the guy who suggested k-vertex cover had something else in mind I'd love to hear it.