Asymmetry in k-Center Variants

Inge Li Gørtz, Anthony Wirth

Publikation: Bog / Antologi / Rapport / Ph.D.-afhandlingRapportForskning

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.
OriginalsprogEngelsk
UdgivelsesstedCopenhagen
ForlagIT-Universitetet i København
UdgaveTR-2003-24
Antal sider14
ISBN (Elektronisk)87-7949-033-6
StatusUdgivet - 2003
Udgivet eksterntJa
NavnIT University Technical Report Series
NummerTR-2003-24
ISSN1600-6100

Fingeraftryk

Dyk ned i forskningsemnerne om 'Asymmetry in k-Center Variants'. Sammen danner de et unikt fingeraftryk.

Citationsformater