Pregled bibliografske jedinice broj: 474288
Improved Approximations for Guarding 1.5-Dimensional Terrains
Improved Approximations for Guarding 1.5-Dimensional Terrains // Algorithmica, 60 (2011), 2; 451-463 doi:10.1007/s00453-009-9358-4 (međunarodna recenzija, članak, znanstveni)
CROSBI ID: 474288 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
Improved Approximations for Guarding 1.5-Dimensional Terrains
Autori
Elbassioni, Khaled ; Krohn, Erik ; Matijević, Domagoj ; Mestre, Julián ; Ševerdija, Domagoj
Izvornik
Algorithmica (0178-4617) 60
(2011), 2;
451-463
Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni
Ključne riječi
terrain guarding; approximation algorithms; totally balanced matrices; geometric covering problems
Sažetak
We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the previous best approximation factor of 5 (see King in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 629–640, 2006). Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic 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
