Tata Institute of Fundamental Research
Refined Approaches to Randomized Rounding
Seminar
Speaker:
Nikhil Bansal
Eindhoven University of Technology
Department of Maths. & Computing Science
HG 9.01
P.O. Box 513
5600 MB Eindhoven
The Netherlands
Organiser:
John Barretto
Date:
Tuesday, 3 Jan 2012, 11:30 to 12:30
Venue:
AG-69
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Nikhil Bansal Eindhoven University of Technology Department of Maths. & Computing Science HG 9.01 P.O. Box 513 5600 MB Eindhoven The Netherlands |
| Organiser: | John Barretto |
| Date: | Tuesday, 3 Jan 2012, 11:30 to 12:30 |
| Venue: | AG-69 |
(Scan to add to calendar)
Abstract:
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.