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.