Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
One-Dimensional r-Gathering Under Uncertainty
verfasst von : Shareef Ahmed, Shin-ichi Nakano, Md. Saidur Rahman
Erschienen in: Algorithmic Aspects in Information and Management
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 \in C\) to a facility \(f \in 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^\frac{n}{r})\log mn)\) and \(O(mn\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.