Tata Institute of Fundamental Research
Local Search for Geometric Set Cover Problems
Seminar
Speaker:
Kasturi Varadarajan
University of Iowa
Department of Computer Science
Iowa City, IA 52242-1419
United States
Date:
Wednesday, 28 Jul 2010 (all day)
Venue:
D-405
(Scan to add to calendar)
Abstract:
In SocG 2009, Mustafa and Ray showed that a local search algorithm is, somewhat surprisingly, a PTAS for certain geometric set cover/hitting set problems. In this context, a PTAS is a scheme that for any eps > 0, yields an algorithm that runs in polynomial time and returns a solution whose size is at most (1 + eps) times that of the optimal set cover/hitting set. A similar PTAS was presented by Chan and Har-Peled at the same conference for the largest independent set problem in certain geometric intersection graphs.
We will discuss a hitting set result of Mustafa and Ray and, time permitting, an application of their machinery to a terrain guarding problem by Gibson, Kanade, Krohn, and the speaker.
| Speaker: | Kasturi Varadarajan University of Iowa Department of Computer Science Iowa City, IA 52242-1419 United States |
| Date: | Wednesday, 28 Jul 2010 (all day) |
| Venue: | D-405 |
(Scan to add to calendar)
Abstract:
In SocG 2009, Mustafa and Ray showed that a local search algorithm is, somewhat surprisingly, a PTAS for certain geometric set cover/hitting set problems. In this context, a PTAS is a scheme that for any eps > 0, yields an algorithm that runs in polynomial time and returns a solution whose size is at most (1 + eps) times that of the optimal set cover/hitting set. A similar PTAS was presented by Chan and Har-Peled at the same conference for the largest independent set problem in certain geometric intersection graphs.
We will discuss a hitting set result of Mustafa and Ray and, time permitting, an application of their machinery to a terrain guarding problem by Gibson, Kanade, Krohn, and the speaker.
We will discuss a hitting set result of Mustafa and Ray and, time permitting, an application of their machinery to a terrain guarding problem by Gibson, Kanade, Krohn, and the speaker.