Seminar by Daya Gaur
Decompose and Round
Daya Gaur
Department of Mathematics and Computer Science, University of Lethbridge
Date: Friday, September 25, 2009
Time: 3:30 PM
Venue: CS101.Abstract:
We will describe a simple deterministic method to round fractional variables for some covering programs. We group the fractional variables such that the resulting problem has a "nice" structure. Rounding is then achieved using some combinatorial algorithm. We will illustrate the technique on a couple of problems. The approach yields current best known approximation ratio for the rectangle stabbing problem, array partition problem, and a terrain guarding problem. Back to Seminars in 2009-10