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. 837-845, 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|\log|F|)$-time algorithm
to solve the $r$-gathering problem are known.
In this paper we give a simple $O(|C|+r^2|F|)$-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$-gather-clustering 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$-gather-clustering is a partition of the points
into clusters such that each cluster has at least $r$ points.
The cost of an $r$-gather-clustering 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$-gather-clustering problem is the problem to find
the $r$-gather-clustering 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
|