Algorithmic Chernoff-Hoeffding Inequalities in Integer Programming
Srivastav, Anand and Stangier, Peter
(1996)
Algorithmic Chernoff-Hoeffding Inequalities in Integer Programming.
Published in:
Random structures & algorithms Vol. 8 (1).
pp. 27-58.
Abstract
Proofs of classical Chernoff-Hoeffding bounds have been used to obtain polynomial-time implementations of Spencer's derandomization method of conditional probabilities on usual finite machine models: given m events whose complements are large deviations corresponding to weighted sums of n mutually independent Bernoulli trials, Raghavan's lattice approximation algorithm constructs for 0-1 weights and integer deviation terms in O(mn)-time a point for which all events hold. For rational weighted sums of Bernoulli trials the lattice approximation algorithm or Spencer's hyperbolic cosine algorithm are deterministic procedures, but a polynomial-time implementation was not known. We resolve this problem with an O(mn^2log frac{mn}{epsilon})-time algorithm, whenever the probability that all events hold is at least epsilon > 0. Since such algorithms simulate the proof of the underlying large deviation inequality in a constructive way, we call it the algorithmic version of the inequality. Applications to general packing integer programs and resource constrained scheduling result in tight and polynomial-time approximations algorithms.
Download: |
Download (315kB) | Preview |
---|---|
Editorial actions: | ![]() |
ZAIK Number: | zpr93-147 |
---|---|
Depositing User: | Archive Admin |
Date Deposited: | 02 Apr 2001 00:00 |
Last Modified: | 19 Jan 2012 10:35 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/147 |