Improved Approximations for Guarding 1.5-Dimensional Terrains - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Improved Approximations for Guarding 1.5-Dimensional Terrains

Khaled Elbassioni
  • Fonction : Auteur
  • PersonId : 857915
Erik Krohn
  • Fonction : Auteur
  • PersonId : 857916
Domagoj Matijevic
  • Fonction : Auteur
  • PersonId : 857917
Julián Mestre
  • Fonction : Auteur
  • PersonId : 857918
Domagoj Severdija
  • Fonction : Auteur
  • PersonId : 857919

Résumé

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 currently best approximation factor of 5 (see [14]). 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.
Fichier principal
Vignette du fichier
30-elbassioni.pdf (200.86 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00359652 , version 1 (09-02-2009)

Identifiants

  • HAL Id : inria-00359652 , version 1

Citer

Khaled Elbassioni, Erik Krohn, Domagoj Matijevic, Julián Mestre, Domagoj Severdija. Improved Approximations for Guarding 1.5-Dimensional Terrains. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.361-372. ⟨inria-00359652⟩

Collections

STACS2009
69 Consultations
262 Téléchargements

Partager

Gmail Facebook X LinkedIn More