Tata Institute of Fundamental Research
On Weighted Geometric Set Cover
Seminar
Speaker:
Kasturi Varadarajan
University of Iowa
Department of Computer Science
101E, Maclean Hall
Iowa City, IA 52242-
Date:
Wednesday, 21 Jul 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
There has been much progress on geometric set cover problems, but most known techniques only apply to the unweighted setting. For the weighted setting, very few results are known with approximation guarantees better than that for the combinatorial set cover problem. In this talk, we employ the idea of quasi-uniform sampling to obtain improved approximation guarantees in the weighted setting for a large class of problems for which such guarantees were known in the unweighted case.
| Speaker: | Kasturi Varadarajan University of Iowa Department of Computer Science 101E, Maclean Hall Iowa City, IA 52242- |
| Date: | Wednesday, 21 Jul 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
There has been much progress on geometric set cover problems, but most known techniques only apply to the unweighted setting. For the weighted setting, very few results are known with approximation guarantees better than that for the combinatorial set cover problem. In this talk, we employ the idea of quasi-uniform sampling to obtain improved approximation guarantees in the weighted setting for a large class of problems for which such guarantees were known in the unweighted case.