The Capacitated K-Center Problem

Loading...
Thumbnail Image

Files

CS-TR-3651.ps (279.14 KB)
No. of downloads: 267
CS-TR-3651.pdf (261.13 KB)
No. of downloads: 1109

Publication or External Link

Date

1998-10-15

Advisor

Citation

DRUM DOI

Abstract

The capacitated $K$-center problem is a fundamental facility location problem, where we are asked to locate $K$ facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. Moreover, each facility may be assigned at most $L$ vertices. This problem is known to be NP-hard. We give polynomial time approximation algorithms for two different versions of this problem that achieve approximation factors of 5 and 6. We also study some generalizations of this problem. (Also cross-referenced as UMIACS-TR-96-39)

Notes

Rights