Asymmetric k-Center with Minimum Coverage

Inge Li Gørtz

Research output: Book / Anthology / Report / Ph.D. thesisReportResearch

Abstract

In this paper we give approximation algorithms and inapproximability results for various asymmetric k-center with minimum coverage problems. In the k-center with minimum coverage problem, each center is required to serve a minimum number of clients. These problems have been studied by Lim et al. [Theor. Comput. Sci. 2005] in the symmetric setting. In the q-all-coverage k-center problem each center must serve at least q vertices (including itself). In the q-coverage k-center problem each center must serve at least q non-center nodes. We provide O(log∗ n)-approximation algorithms for the asymmetric q-all-coverage and q-coverage problems in both the unweighted and weighted case. This is optimal within a constant factor. Lim et al. also study the q-coverage k-supplier problem and the priority version of all the mentioned problems in the symmetric setting. We show that the asymmetric q-coverage k-supplier problem and the priority versions of asymmetric q-coverage k-center and asymmetric q-all-coverage k-center are inapproximable.
Original languageEnglish
Place of PublicationCopenhagen
PublisherIT-Universitetet i København
EditionTR-2005-66
Number of pages13
ISBN (Electronic)87-7949-096-4
Publication statusPublished - 2005
Externally publishedYes
SeriesIT University Technical Report Series
NumberTR-2005-66
ISSN1600-6100

Fingerprint

Dive into the research topics of 'Asymmetric k-Center with Minimum Coverage'. Together they form a unique fingerprint.

Cite this