Journal
THEORETICAL COMPUTER SCIENCE
Volume 332, Issue 1-3, Pages 1-17Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2004.08.010
Keywords
approximation algorithm; k-center problem; minimum coverage
Categories
Ask authors/readers for more resources
In this work, we study an extension of the k-center facility location problem, where centers are required to service a minimum of clients. This problem is motivated by requirements to balance the workload of centers while allowing each center to cater to a spread of clients. We study three variants of this problem, all of which are shown to be N P-hard. In-approximation hardness and approximation algorithms with factors equal or close to the best lower bounds are provided. Generalizations, including vertex costs and vertex weights, are also studied. (c) 2004 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available