Nalazite se na CroRIS probnoj okolini. Ovdje evidentirani podaci neće biti pohranjeni u Informacijskom sustavu znanosti RH. Ako je ovo greška, CroRIS produkcijskoj okolini moguće je pristupi putem poveznice www.croris.hr
izvor podataka: crosbi

Guarding 1.5D Terrains with Demands (CROSBI ID 193440)

Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija

Elbassioni, Khaled ; Matijević, Domagoj ; Ševerdija, Domagoj Guarding 1.5D Terrains with Demands // International journal of computer mathematics, 89 (2012), 16; 2143-2151. doi: 10.1080/00207160.2012.707800

Podaci o odgovornosti

Elbassioni, Khaled ; Matijević, Domagoj ; Ševerdija, Domagoj

engleski

Guarding 1.5D Terrains with Demands

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.

1.5D terrain guarding; LP relaxation; totally balanced matrices; demands; approximation algorithm

nije evidentirano

nije evidentirano

nije evidentirano

nije evidentirano

nije evidentirano

nije evidentirano

Podaci o izdanju

89 (16)

2012.

2143-2151

objavljeno

0020-7160

10.1080/00207160.2012.707800

Povezanost rada

Računarstvo, Matematika

Poveznice
Indeksiranost