Sandro
Bosio
Title:
Hyperbolic set covering problems with competing ground-set
elements
Abstract:
We investigate a new nonlinear variant of the set covering
problem where each
ground-set element competes with all its neighbors (i.e., elements
sharing
a covering subset with it) for access to a given resource, and resource
allocation is fair. In particular, motivated by a challenging problem
arising
in wireless network design, we consider a hyperbolic objective function
that
privileges covers with small subsets and with limited overlaps. 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, investigate linearization techniques
and
present an efficient Lagrangean relaxation approach to tackle
medium-scale
instances. Time permitting, we will also mention some application
related
aspects. Joint work with Edoardo Amaldi and Federico Malucelli, DEI,
Politecnico di Milano.
slides