Cooperative covering problems on networks. Issue 4 (20th March 2014)

• Record Type: Journal Article
• Authors: Averbakh, Igor; Berman, Oded; Krass, Dmitry; Kalcsics, Jörg; Nickel, Stefan
• Is Part Of: Networks. Volume 63:Issue 4(2014:Jul.)
• Page Start: 334
• Page End: 349
• Publication Date: 2014-03-20
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21549
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>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 <italic>p</italic>‐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</p> </abstract>