Event calendar file
School of Technology and Computer Science Seminars
Refined Approaches to Randomized Rounding
by Dr. Nikhil Bansal (Eindhoven University of Technology, The Netherlands)
Tuesday, January 3, 2012
from
to
(Asia/Kolkata)
at Colaba Campus ( AG-69 )
at Colaba Campus ( AG-69 )
| Description |
Randomized rounding is a classic method to produce an integral 0/1 solution from a fractional one by interpreting the fractions as probabilities. However, in many situations this rounding is too naive and loses various nice properties that the fractional solution may have possessed. We will survey various dependent rounding approaches developed in recent years that achieve the benefits of randomized rounding while maintaining other desirable properties. In particular, we will see how several recent results such as sub-logarithmic approximation for asymmetric TSP, constructive algorithms for discrepancy minimization and additive guarantees for degree bounded spanning trees can be viewed from this lens. |
