Algorithms Seminar

Randomized Rounding Revisited

Speaker:Sandeep Sen
Date: Friday, June 30, 2017
Time: 1:30pm - 2:30pm
Location: D344 LSRC, Duke

Abstract

We develop new techniques for rounding packing integer programs using iterative randomized rounding. It is based on a novel application of multidimensional Brownian motion in R^n. Let ~x ∈ [0,1]^n be a fractional feasible solution of a packing constraint A x ≤ 1, A ∈ {0,1 }^{m X n} that maximizes a linear objective function. Our algorithm iteratively transforms ~x to ^x ∈ {0,1}^n using a random walk, such that the expected values of ^x_i's are consistent with the Raghavan-Thompson rounding. In addition, it gives us intermediate values x' which can then be used to bias the rounding towards a superior solution. Our algorithm gradually sparsifies A to A’ ∈ {0,1}^{m X n} where each row in A’ has ≤ \log n non-zero coefficients with ≤ O(1). The reduced dependencies between the constraints of the sparser system can be exploited using Lovasz Local Lemma. Using the Moser-Tardos' constructive version, x' converges to ^x in polynomial time to a distribution over the unit hypercube H_n = {0,1}^n such that the expected value of any linear objective function over H_n equals the value at ~x. We discuss application of these techniques when A is a random matrix and also for a more general situation of a k-column sparse matrix. Joint work with Dhiraj Madan.

Biography

Professor Sandeep Sen obtained his BTech in CS from IIT Kharagpur, MS from UC Santa Barbara and PhD from Duke University in 1989. After a brief stint in Bell Labs, Murray Hill, he has been a faculty in IIT Delhi since 1991. He has held Visiting positions in UNC Chapel Hill, Univ of Connecticut, MPI Saarbrucken, BRICS and MSR Bangalore and ISI Kolkata. His research interests span Algorithms and Complexity. Prof Sen is a Fellow of the Indian Academy of Sciences and the Indian National Science Academy. He is a former Head of Dept of CSE and presently Dean Faculty in IIT Delhi.

Hosted by:
Debmalya Panigrahi