Distributed approximation of cellular coverage

We consider the following model of cellular networks. Each base station has a given finite capacity, and each client has some demand and profit. A client can be covered by a specific subset of the base stations, and its profit is obtained only if its demand is provided in full. The goal is to assign clients to base stations, so that the overall profit is maximized subject to base station capacity constraints.In this work, we present a distributed algorithm for the problem, that runs in polylogarithmic time, and guarantees an approximation ratio close to the best known ratio achievable by a centralized algorithm.

► Detailed model: base stations have capacities, and clients have demands and profits.
► Accessibility model: each client can be covered only by some specific base stations.
► Goal model: only clients receiving their full demand from one base station pay.
► Algorithm complexity: polylogarithmic number of rounds.
► Profit guarantee: constant fraction of the optimal in the worst case.