Paper Info
Title
A Simple Algorithm For R-Gatherings On The Line
Abstract
In this paper we study recently proposed variant of the facility location problem called the r-gathering problem. Given sets C and F of points on the plane and distance d(c, f) for each c is an element of C and f is an element of F, an r-gathering of C to F is an assignment A of C to open facilities F' subset of F such that r or more customers are assigned to each open facility. The cost of an r-gathering is the maximum distance d(c, f) between c is an element of C and A(c) is an element of F' among the assignment, which is max(c is an element of C){d(c,A(c))}. The r-gathering problem finds the r-gathering minimize the cost. A polynomial time 3-approximation algorithm for the r-gathering problem is known. When all C and F are on the line an O(vertical bar C vertical bar+vertical bar F vertical bar)log(vertical bar C vertical bar+vertical bar F vertical bar)) time algorithm and an O(vertical bar C vertical bar + vertical bar F vertical bar log(2) r vertical bar +vertical bar F vertical bar log vertical bar F vertical bar) time algorithm to solve the r-gathering problem are known. In this paper we give a simple O(vertical bar C vertical bar +r(2)vertical bar F vertical bar) time algorithm to solve the r-gathering problem. Since in typical case r << vertical bar F vertical bar << vertical bar C vertical bar holds our new algorithm is faster than the known algorithms.
Year
DOI
Venue
2018
10.1007/978-3-319-75172-6_1
WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2018
Keywords
Field
DocType
Algorithm, Facility location, Gathering
Discrete mathematics,Combinatorics,Computer science,SIMPLE algorithm,Time complexity
Conference
Volume
ISSN
Citations 
10755
0302-9743
0
PageRank 
References 
Authors
0.34
3
1
Name
Order
Citations
PageRank
Shin-ichi Nakano124624.40