Let C be a set of n customers and F be a set of m facilities. An r-gathering of C is an assignment of each customer c ∈ C to a facility f ∈ F such that each facility has zero or at least r customers. The r-gathering problem asks to find an r-gathering that minimizes the maximum distance between a customer and its facility. In this paper we study the r-gathering problem when the customers and the facilities are on a line, and each customer location is uncertain. We show that, the r-gathering problem can be solved in O(nk + mn log n + (m + n log k + n log n + nr~(n/r)) log mn) and O(rnn log n + (n log n + m) log mn) time when the customers and the facilities are on a line, and the customer locations are given by piecewise uniform functions of at most k + 1 pieces and "well-separated" uniform distribution functions, respectively.
展开▼
机译：让C成为一组客户，F是一套M设施。 C的R收集是每个客户C≠C的分配给设施f∈F，使得每个设施具有零或至少的客户。 R收集问题要求找到r-grentiping，最小化客户与其设施之间的最大距离。在本文中，我们研究了客户和设施在一条线上的r收集问题，每个客户位置都不确定。我们表明，r收集问题可以在o（nk + m log n +（m + n log k + n log n + nr〜（n / r））log mn）和o（rnn log n + （n log n + m）log mn）客户和设施在一行中的时间，并且客户位置通过分段均匀函数，分别为“分离良好的”均匀分布函数。
展开▼
