Premium
Cooperative covering problems on networks
Author(s) -
Averbakh Igor,
Berman Oded,
Krass Dmitry,
Kalcsics Jörg,
Nickel Stefan
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21549
Subject(s) - heuristics , mathematical optimization , integer programming , linear programming , signal (programming language) , facility location problem , signal strength , computer science , piecewise , set (abstract data type) , piecewise linear function , point (geometry) , polynomial , function (biology) , algorithm , mathematics , wireless sensor network , computer network , mathematical analysis , geometry , evolutionary biology , biology , programming language
In this article, we consider the cooperative maximum covering location problem on a network. In this model, it is assumed that each facility emits a certain “signal” whose strength decays over distance according to some “signal strength function.” A demand point is covered if the total signal transmitted from all the facilities exceeds a predefined threshold. The problem is to locate facilities so as to maximize the total demand covered. For the 2‐facility problem, we present efficient polynomial algorithms for the cases of linear and piecewise linear signal strength functions. For the p ‐facility problem, we develop a finite dominant set, a mixed‐integer programming formulation that can be used for small instances, and two heuristics that can be used for large instances. The heuristics use the exact algorithm for the 2‐facility case. We report results of computational experiments. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 334–349 2014