Guarding 1.5D terrains with demands

Khaled Elbassioni, Domagoj Matijević, Domagoj Ševerdija

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In this paper, we consider the 1.5D terrain guarding problem in which every point on the terrain that is to be covered has an integer demand associated with it. The goal is to find a minimum cardinality set of guards such that each point is guarded by a number of guards satisfying its demand. We present a first constant-factor approximation algorithm for the problem, that is, a 5/2(1+1/dmin)-approximation algorithm, where dmin is a minimum demand. The algorithm is based on solving appropriate subproblems established by a decomposition of the main problem due to linear programming relaxation of the corresponding covering problem.

Original languageBritish English
Pages (from-to)2143-2151
Number of pages9
JournalInternational Journal of Computer Mathematics
Volume89
Issue number16
DOIs
StatePublished - 1 Nov 2012

Keywords

  • 1.5D terrain guarding
  • Approximation algorithm
  • Demands
  • LP relaxation
  • Totally balanced matrices

Fingerprint

Dive into the research topics of 'Guarding 1.5D terrains with demands'. Together they form a unique fingerprint.

Cite this