ALGORITHMIC CHERNOFF-HOEFFDING INEQUALITIES IN INTEGER PROGRAMMING

Proofs of classical Chernoff-Hoeffding bounds has been used to obtain polynomial-time implementations of Spencer's derandomization method of conditional probabilities on usual finite machine models: given m eve nts whose complements are large deviations corresponding to weighted s ums of n mutually independent Bernoulli trials, Raghavan's lattice app roximation algorithm constructs for 0-1 weights, and integer deviation terms in O(mn)-time a point for which all events hold. For rational w eighted sums of Bernoulli trials the lattice approximation algorithm o r Spencer's hyperbolic cosine algorithm are deterministic precedures, but a polynomial-time implementation was not known. We resolve this pr oblem with an O(mn(2) log mn/epsilon)-time algorithm, whenever the pro bability that all events hold is at least epsilon > O. Since such algo rithms simulate the proof of the underlying large deviation inequality in a constructive way, we call it the algorithmic version of the ineq uality. Applications to general packing integer programs and resource constrained scheduling result in tight and polynomial-time approximati ons algorithms. (C) 1996 John Wiley & Sons, Inc.