Pregled bibliografske jedinice broj: 631725
Guarding 1.5D Terrains with Demands
Guarding 1.5D Terrains with Demands // International journal of computer mathematics, 89 (2012), 16; 2143-2151 doi:10.1080/00207160.2012.707800 (međunarodna recenzija, članak, znanstveni)
CROSBI ID: 631725 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
Guarding 1.5D Terrains with Demands
Autori
Elbassioni, Khaled ; Matijević, Domagoj ; Ševerdija, Domagoj
Izvornik
International journal of computer mathematics (0020-7160) 89
(2012), 16;
2143-2151
Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni
Ključne riječi
1.5D terrain guarding; LP relaxation; totally balanced matrices; demands; approximation algorithm
Sažetak
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, i.e a $5/2(1 + 1/d_\min)$- approximation algorithm, where $d_\min$ is a minimum demand. The algorithm is based on solving appropriate subproblems established by a decomposition of the main problem dictated by the linear programming relaxation of the corresponding covering problem.
Izvorni jezik
Engleski
Znanstvena područja
Matematika, Računarstvo
POVEZANOST RADA
Ustanove:
Sveučilište u Osijeku, Odjel za matematiku
Citiraj ovu publikaciju:
Časopis indeksira:
- Current Contents Connect (CCC)
- Web of Science Core Collection (WoSCC)
- Science Citation Index Expanded (SCI-EXP)
- SCI-EXP, SSCI i/ili A&HCI
- Scopus
