Given an unweighted, undirected graph, we can use the classical 2-appx for $k$-center to select a set $S$ of centers such that every vertex is within a distance of 2 of some center in $S$.

Note that this procedure often selects fewer than $k$ centers since it only needs to cover everything with a radius of 2, while OPT covers everything (with $k$ centers) with a radius of 1.

I am considering a stronger version of the $k$-center problem:

Is there a way to select $k$ centers in a graph such that there is an OPTIMAL set of centers $S^*$ with every node in $S^*$ adjacent to a node we select?

I suspect that an algorithm for this problem should use the Hochbaum-Shmoys procedure to select some $k'$ centers, then place the extra centers in some clever way to ensure the stronger condition.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.