Asymmetry in k-Center Variants
TR-2003-24, Authors: Inge Li Gørtz and Anthony Wirth Inge Li Gørtz Anthony Wirth
This report explores three concepts: the k-center problem, its variants, and asymmetry.
We demonstrate an O(log* n)-approximation algorithm for the asymmetric weighted k-center problem. For the p-neighbor k-center problem we give an O(log* k)-bicriteria algorithm using 2k centers, for small p.
Turning to approximability we show that the priority k-center problem, the k-supplier problem, and the k-center problem with outliers and forbidden centers are inapproximable. These versions all admit constant factor algorithms in the symmetric case.
Technical report TR-2003-24 in IT University Technical Report Series, June 2003.
Available as PDF