Cooperative covering problems on networks

Igor Averbakh, Oded Berman, Dmitry Krass, Jörg Kalcsics*, Stefan Nickel

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)334-349
Number of pages16
JournalNetworks
Volume63
Issue number4
Early online date20 Mar 2014
DOIs
Publication statusPublished - Jul 2014

Keywords

  • cooperative
  • covering problems
  • finite dominating sets
  • integer programming formulations
  • networks

Fingerprint

Dive into the research topics of 'Cooperative covering problems on networks'. Together they form a unique fingerprint.

Cite this