





























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。