On r-Gatherings on the Line

Toshihiro AKAGI  Shin-ichi NAKANO  

IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.3   pp.428-433
Publication Date: 2017/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016FCP0007
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)
algorithm,  facility location,  

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

In this paper we study a recently proposed variant of the facility location problem, called the r-gathering problem. Given an integer r, a set C of customers, a set F of facilities, and a connecting cost co(c, f) for each pair of cC and fF, an r-gathering of customers C to facilities F is an assignment A of C to open facilities F'F such that at least r customers are assigned to each open facility. We give an algorithm to find an r-gathering with the minimum cost, where the cost is maxcC{co(c, A(c))}, when all C and F are on the real line.