ITU / Research / Technical Reports / Technical Reports Archive / 2003 / Asymmetry in k-Center Variants

Asymmetry in k-Center Variants

TR-2003-24, Authors: Inge Li Gørtz and Anthony Wirth

June 2003

Abstract

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.