  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 $\mathbb{R}^n$. Let $\overset{\sim}{x} \in
{[0,1]}^n$ be a fractional feasible solution of a packing constraint $A x \leq
1,\ \ $ $A \in {\{0,1 \}}^{m\times n}$ that maximizes a linear objective
function. The independent randomized rounding method of Raghavan-Thompson
rounds each variable $x_i$ to 1 with probability $\overset{\sim}{x_i}$ and 0
otherwise. The expected value of the rounded objective function matches the
fractional optimum and no constraint is violated by more than $O(\frac{\log m}
{\log\log m})$.In contrast, our algorithm iteratively transforms
$\overset{\sim}{x}$ to $\hat{x} \in {\{ 0,1\}}^{n}$ using a random walk, such
that the expected values of $\hat{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.The
reduced dependencies between the constraints of the sparser system can be
exploited using {\it Lovasz Local Lemma}. For $m$ randomly chosen packing
constraints in $n$ variables, with $k$ variables in each inequality, the
constraints are satisfied within $O(\frac{\log (mkp\log m/n) }{\log\log
(mkp\log m/n)})$ with high probability where $p$ is the ratio between the
maximum and minimum coefficients of the linear objective function. Further, we
explore trade-offs between approximation factors and error, and present
applications to well-known problems like circuit-switching, maximum independent
set of rectangles and hypergraph $b$-matching. Our methods apply to the
weighted instances of the problems and are likely to lead to better insights
for even dependent rounding.
