Algorithms for r-gathering and r-gather clustering problems

Abstract

Given a set of customers C, a set of proposed facilities F , an opening cost op(f ) of each facility f ∈ F and a cost function cost(c, f ) for each c ∈ C and f ∈ F , the facility location problem asks to find an assignment of customers to facilities such that a designated cost is minimized. Because of the absence of lower bound on the number of customers assigned to each facility, the number of customers assigned to a facility can be small. To address this problem, recently a new variant of facility location problem called the r-gathering problem is introduced. An r-gathering is an assignment of customers to the facilities such that each facility serves zero or at least r customers. The r-gathering problem asks to find an r-gathering which minimizes the maximum distance between a customer and its facility. A seemingly related problem called the r-gather clustering problem asks to partition a set of points P into some clusters such that each cluster has at least r points and the maximum distance between two points in the same cluster is minimum. Both the r-gathering and r-gather clustering problems can be used to find locations for establishing shelters with limited capacity and an assignment of residents to shelters that can minimize the evacuation span in time of disaster. Both the problems are NP-hard in general, and polynomial time algorithms are known when the customers and facilities are on a line. In this thesis, we attempt to reduce the distance between the two results. We consider r- gathering and r-gather clustering problems when the customer and facilities are on a “star” and give algorithms for the problems which run in polynomial time if the degree of the star is constant. We also consider the uncertain r-gathering problem where the customer locations are given as probability density functions. We give an exact exponential algorithm for the uncertain r-gathering problem on a line when the customer locations are specified by histograms. We also give a polynomial time algorithm for a restricted case when customer locations are given as well-separated uniform distributions.