Can I read Improved Randomized Rounding using Random Walks on EtoBox?

Improved Randomized Rounding using Random Walks by Sen, Sandeep is a scholarly article available to read on EtoBox.

What is Improved Randomized Rounding using Random Walks about?

We describe a novel algorithm for rounding packing integer programs based on multidimensional Brownian motion in $\mathbb{R}^n$. Starting from an optimal fractional feasible solution $\bar{x}$, the procedure converges in polynomial time to a distribution over (possibly infeasible) point set $P \subset {\{0,1 \}}^n$ such that the expected value of any linear objective function over $P$ equals the value at $\bar{x}$. This is an alternate approach to the classical randomized rounding method of Raghavan and Thompson \cite{RT:87}. Our procedure is very general and in conjunction with discrepancy based arguments, yield efficient alternate methods for rounding other optimization problems that can be expressed as packing ILPs including disjoint path problems and MISR.

Author

Sen, Sandeep

Published

2014

Language

EN