The Priority k-Median Problem

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:

Related URL:


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