I thought of this problem and I was wondering if there is any polynomial time solution?
Given a weighted tree of N nodes, pick K nodes such that sum of distances from each node to the nearest picked node is minimized.
For K = 1, the answer is the centroid of the tree. What about K > 1 ?