Asymmetry in k-Center Variants
- Inge Li Gørtz,
- Anthony Wirth
- Princeton University
Research Output:
Book / Anthology / Report
Report
Open access
Publication Information
Output type
Research Output:
Book / Anthology / Report
Report
Original language
EnglishPublication milestones
- Published - 2003
Publication status
Published - 2003
Place of publication
CopenhagenEdition
TR-2003-24Publisher
IT-Universitetet i København, DenmarkBook series
- Book series name: IT University Technical Report Series
Series number: TR-2003-24
ISSN: 1600-6100
ISBN (Electronic)
87-7949-033-6Abstract
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.
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.
Access to documents
Final published version, 145.74 KB