Universität zu Köln

Srivastav, Anand and Stangier, Peter (1996). Algorithmic Chernoff-Hoeffding Inequalities in Integer Programming. Wiley. ['eprint_fieldopt_monograph_type_preprint' not defined].

Preview

PDF zpr93-147.pdf Download (372kB) | Preview

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.

Item Type:	Monograph (['eprint_fieldopt_monograph_type_preprint' not defined])
Creators:	Creators Email ORCID ORCID Put Code Srivastav, Anand UNSPECIFIED UNSPECIFIED UNSPECIFIED Stangier, Peter UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-546822
Journal or Publication Title:	Random structures & algorithms
Number:	1
Page Range:	pp. 27-58
Date:	1996
Publisher:	Wiley
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54682