ARTICLE DOWNLOAD

The Distance-Constrained Matroid Median Problem

10.00$
ARTICLE DOWNLOAD

The Distance-Constrained Matroid Median Problem

10.00$

Naoyuki Kamiyama 

Abstract

Alamdari and Shmoys introduced the following variant of the k-median problem. In this variant, we are given an instance of the k-median problem and a threshold value. Then this variant is the same as the k-median problem except that if the distance between a client i and a facility j is more than the threshold value, then i is not allowed to be connected to j. In this paper, we consider a matroid generalization of this variant of the k-median problem. First, we introduce a generalization of this variant in which the constraint on the number of opened facilities is replaced by a matroid constraint. Then we propose a polynomial-time bicriteria approximation algorithm for this problem by combining the algorithm of Alamdari and Shmoys and the algorithm of Krishnaswamy, Kumar, Nagarajan, Sabharwal, and Saha for a matroid generalization of the k-median problem.

Only units of this product remain
Year 2020
Language English
Format PDF
DOI 10.1007/s00453-020-00688-5