r-Gatherings" /> r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r (≥ 2) or more customers are assigned to each open facility. (Each facility needs enough number of customers for its opening.) Then the r-gathering problem finds an r-gathering minimizing a designated cost. Armon gave a simple 3-approximation algorithm for the r-gathering problem and proved that with assumption P ≠ NP the problem cannot be approximated within a factor of less than 3 for any r ≥ 3. The running time of the 3-approximation algorithm is O(|C||F|+r|C|+|C|log|C|)). In this paper we improve the running time of the algorithm by (1) removing the sort in the algorithm and (2) designing a simple but efficient data structure." /> r-Gatherings" />
[go: up one dir, main page]

Faster Min-Max r-Gatherings

Toshihiro AKAGI
Ryota ARAI
Shin-ichi NAKANO

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A    No.6    pp.1149-1151
Publication Date: 2016/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1149
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
facility location problem,  

Full Text: PDF(64.7KB)>>
Buy this Article


Summary: 
An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r (≥ 2) or more customers are assigned to each open facility. (Each facility needs enough number of customers for its opening.) Then the r-gathering problem finds an r-gathering minimizing a designated cost. Armon gave a simple 3-approximation algorithm for the r-gathering problem and proved that with assumption P ≠ NP the problem cannot be approximated within a factor of less than 3 for any r ≥ 3. The running time of the 3-approximation algorithm is O(|C||F|+r|C|+|C|log|C|)). In this paper we improve the running time of the algorithm by (1) removing the sort in the algorithm and (2) designing a simple but efficient data structure.

open access publishing via