Kumar, Amit ; Sabharwal, Yogish (2007) The Priority k-Median Problem Lecture Notes in Computer Science, 4855 . pp. 71-83. ISSN 0302-9743
Full text not available from this repository.
Official URL: http://doi.org/10.1007/978-3-540-77050-3_6
Related URL: http://dx.doi.org/10.1007/978-3-540-77050-3_6
Abstract
In this paper, we consider a generalized version of the k-median problem in metric spaces, called the priority k-median problem in which demands and facilities have priorities associated with them and a demand can only be assigned to a facility that has the same priority or better. We show that there exists a polynomial time constant factor approximation algorithm for this problem when there are two priorities. We also show that the natural integer program for the problem has an arbitrarily large integrality gap when there are four or more priorities.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag. |
| ID Code: | 123541 |
| Deposited On: | 30 Sep 2021 09:54 |
| Last Modified: | 30 Sep 2021 09:54 |
Repository Staff Only: item control page
