# 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: |
Postscript
- Preprinted Version
Download (315kB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

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 |