Assigning Proximity Facilities for Gatherings

Abstract

In this paper we study a recently proposed variant of the problem the r-gathering problem. An r-gathering of customers C to facilities F is an assignment A of C to open facilities $F^{'} \subset F$ such that r or more customers are assigned to each open facility. (Each open facility needs enough number of customers.) Then the cost of an r-gathering is $\max \{\max _{i\in C}\{co(i,A(i))\}, \max _{j\in F'}\{op(j) \} \}$, and the r-gathering problem finds an r-gathering having the minimum cost.

Assume that F is a set of locations for emergency shelters, op(f) is the time needed to prepare a shelter $f\in F$, and co(c, f) is the time needed for a person $c\in C$ to reach assigned shelter $A(c)\in F$. Then an r-gathering corresponds to an evacuation plan such that each opened shelter serves r or more people, and the r-gathering problem finds an evacuttion plan minimizing the evacuation time span.

However in a solution above some person may be assigned to a farther open shelter although it has some closer open shelter. It may be difficult for the person to accept such an assignment for an emergency situation. Therefore Armon considered the problem with one more additional constraint, that is, each customer should be assigned to a closest open facility, and gave a 9-approximation algorithm for the problem.

In this paper we give a simple 3-approximation algorithm for the problem.