The Capacitated K-Center Problem
| dc.contributor.author | Khuller, Samir | en_US |
| dc.contributor.author | Sussmann, Yoram J. | en_US |
| dc.date.accessioned | 2004-05-31T22:39:32Z | |
| dc.date.available | 2004-05-31T22:39:32Z | |
| dc.date.created | 1996-06 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.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) | en_US |
| dc.format.extent | 285841 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/822 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3651 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-96-39 | en_US |
| dc.title | The Capacitated K-Center Problem | en_US |
| dc.type | Technical Report | en_US |