Probabilistic construction of deterministic algorithms: approximating packing integer programs (Q1112724)

A matrix \(C_{n\times r}\), \(c_{ij}\in [0,1]\) and a vector \(p=(p_ 1,...,p_ r)\) are given. An integer vector \(q=(q_ 1,...,q_ r)\) that approximates \(p\) is computed. Every coordinate of the vector \(\Delta =C(p- q)\) has to be ``small'' in absolute value. By methods taken from probability theory the author proves the theorem: there exists a vector q such that \(\Delta_ i\leq s_ i\) \(D(s_ i,1/2n)\) for \(s_ i=(c_ i,p)\), where \[ D(m,x)\leq (e-1)(\frac{\ln 1/x}{m})^{1/2},\quad if\quad m>\ln \quad 1/x, \] and \[ D(m,x)\leq \frac{e \ln 1/x}{m \ln ((e \ln 1/x)/m)}, \] otherwise. A deterministic polynomial algorithm is proposed for finding such a vector \(q\). It traces a search tree from a root to some leaf without backtracking. At the next node a component \(q_ i\) is determined by the use of estimates for \(q_ i=0\) and \(q_ i=1\). The procedure, called ``method of conditional probabilities'', is applied to vector selection problems, packing problems and maximum multicommodity flow.