Hyperbolic set covering problems with competing ground-set elements

摘要

Motivated by a challenging problem arising in wireless network design, we investigate a new nonlinear variant of the set covering problem with hyperbolic objective function. Each ground-set element (user) competes with all its neighbors (interfering users) for a shared resource (the network access time), and the goal is to maximize the sum of the resource share assigned to each ground-set element (the network efficiency) while covering all of them. The hyperbolic objective function privileges covers with limited overlaps among selected subsets. In a sense, this variant lies in between the set partitioning problem, where overlaps are forbidden, and the standard set covering problem, where overlaps are not an issue at all. We study the complexity and approximability of generic and Euclidean versions of the problem, present an efficient Lagrangean relaxation approach to tackle medium-to-large-scale instances, and compare the computational results with those obtained by linearizations.