1
$\begingroup$

Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points (in my application, the distances are Manhattan/$L_1$).

For example, given the locations of US cities, we would find an MST that connects to one city from every state.

If helpful, we could additionally assume that the local density of the pointset is upper-bounded (the points can't be clustered too closely). Points of the same color will generally come in groups (can even assume that each color corresponds to a connected region).

A straightforward heuristic would average locations of points of each color, build an MST for those "centers", and then look for shortcuts. Is there something better ?

Points of interest: a proof of NP-hardness, an approximation algorithm, an effective heuristic

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.