Campus Event Calendar
Event Entry
What and Who
Improved Approximations for Guarding 1.5-Dimensional Terrains
Domagoj Matijevic
Josip Juraj Strossmayer University of Osijek, Croatia
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 13 November 2008
14:15
30 Minutes
E1 4
Rotunda 3rd floor
Saarbrücken
Abstract
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.
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. Unlike previous work, our
algorithm generalizes to the weighted and partial versions of the
basic problem.
Contact
Khaled Elbassioni
--email hidden
passcode not visible
logged in users only
Domagoj Matijevic, 11/07/2008 08:20
Khaled Elbassioni, 11/06/2008 14:21 -- Created document.
Khaled Elbassioni, 11/06/2008 14:21 -- Created document.