Refined Approaches to Randomized Rounding

Speaker: 

<p>Nikhil Bansal<br /> Eindhoven University of Technology<br /> Department of Maths. &amp; Computing Science<br /> HG 9.01<br /> P.O. Box 513<br /> 5600 MB Eindhoven<br /> The Netherlands</p>

Time: 

Tuesday, 3 January 2012, 11:30 to 12:30

Venue: 

  • AG-69

Organisers: 

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.