
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

On rGatherings on the Line
Toshihiro AKAGI Shinichi NAKANO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E100D
No.3
pp.428433 Publication Date: 2017/03/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2016FCP0007
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —) Category: Keyword: algorithm, facility location,
Full Text: PDF(196.2KB)>>
Summary:
In this paper we study a recently proposed variant of the facility location problem, called the rgathering 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 c ∈ C and f ∈ F, an rgathering 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 rgathering with the minimum cost, where the cost is max_{c ∈ C}{co(c, A(c))}, when all C and F are on the real line.

