Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the 12th International Conference and Workshops on Algorithms and Computation, WALCOM 2018
DOI: 10.7155/jgaa.00514
A Simple Algorithm for $r$gatherings on the Line
Vol. 23, no. 5, pp. 837845, 2019. Regular paper.
Abstract In this paper we study a 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\in C$ and $f\in F$,
an $r$gathering of $C$ to $F$ is
an assignment $A$ of $C$ to facilities $F^{'} \subset F$
such that $r$ or more customers are assigned to each facility in $F^{'}$.
A facility is open in $A$ if at least one customer is assigned to it.
The cost of an $r$gathering is the maximum distance $d(c,f)$
between $c\in C$ and $A(c)\in F'$
among the assignment,
which is $\max_{c\in C}\{ d(c,A(c)) \}$.
The $r$gathering problem finds the $r$gathering that minimizes the cost.
When all points of $C$ and $F$ are on the line,
an $O((C+F)\log (C+F) )$time algorithm
and
an $O(C+F\log^2 r+F\logF)$time algorithm
to solve the $r$gathering problem are known.
In this paper we give a simple $O(C+r^2F)$time algorithm
to solve the $r$gathering problem.
Since $r<<F<<C$ holds
in a typical case, say evacuation planning,
our new algorithm is $O(\log F)$ factor faster than the known algorithms.
We also give an algorithm to solve a simpler problem,
called the $r$gatherclustering problem, defined as follows.
Given a set $C$ of $n$ points on the plane
and distance for each pair of points in $C$,
an $r$gatherclustering is a partition of the points
into clusters such that each cluster has at least $r$ points.
The cost of an $r$gatherclustering is the maximum radius
among the clusters,
where the radius of a cluster is the minimum radius of the disk
which can cover the points in the cluster.
The $r$gatherclustering problem is the problem to find
the $r$gatherclustering that minimizes the cost.
In this paper
we give an $O(rn)$time simple algorithm to solve the problem
when all points of $C$ are on the line.

Submitted: March 2018.
Reviewed: November 2018.
Revised: December 2018.
Reviewed: February 2019.
Revised: March 2019.
Accepted: April 2019.
Final: September 2019.
Published: October 2019.

Journal Supporters
