3
$\begingroup$

It is well-known that the non-metric $k$-median problem cannot be approximated better than $O(\log(n))$ (by a gap preserving reduction from the set cover problem). Is there any logarithmic approximation algorithms for this problem?

In some real world applications, the cost function does not satisfies the triangle inequality even in a weak sense. Also, the constraint of not having more than $k$ medians cannot be violated and the above approximation ratio is the ratio of solution cost over optimal cost.

$\endgroup$
  • 2
    $\begingroup$ See Neal Young's answer here cstheory.stackexchange.com/questions/12329/… $\endgroup$ – Austin Buchanan Sep 5 '13 at 5:59
  • $\begingroup$ @AustinBuchanan I am looking for an approximation algorithm that does not open more than k medians. This constraint cannot be relaxed in the my application. If I do not miss anything, the algorithm cited by Neal Young opens $O(k\log(n))$ medians. $\endgroup$ – nlc Sep 5 '13 at 17:51
  • $\begingroup$ You can recast the approximation guarantees for existing algorithms to achieve at least some guarantee for opening $k$ facilities. For example, one classical guarantee says that with $k H_n$ facilities, you can achieve assignment cost that is at most the optimal assignment cost achievable with $k$ facilities. This is essentially the same as saying that, with $k$ facilities, you can achieve assignment cost that is at most the optimal assignment cost that can be achieved with $k/H_n$ facilities. $\endgroup$ – Neal Young Dec 9 '15 at 20:29

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.