Universität zu Köln

Srivastav, Anand and Stangier, Peter (1992). On Derandomized Approximation Algorithms. ["eprint_fieldopt_monograph_type_preprint" not defined].

Preview

PDF zpr92-122.pdf Download (343kB) | Preview

Abstract

With the design of powerful randomized algorithms the transformation of a randomized algorithm or probabilistic existence result for combinatorial problems into an efficient deterministic algorithm (called derandomization) became an important issue in algorithmic discrete mathematics. In the last years several interesting examples of derandomization have been published, like discrepancy in hypergraph colouring, packing integer programs and an algorithmic version of the Lovász-Local-Lemma. In this paper the derandomization method of conditional probabilities of Raghavan/Spencer is extended using discrete martingales. As a main result pessimistic estimators are constructed for combinatorial approximation problems involving non-linear objective functions with bounded martingale differences. The theory gives polynomial-time algorithms for the linear and quadratic lattice approximation problem and a quadratic variant of the matrix balancing problem extending results of Spencer, Beck/Fiala and Raghavan. Finally a probabilistic existence result of Erdös on the average graph bisection is transformed into a deterministic algorithm.

Item Type:	Preprints, Working Papers or Reports (["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-546741
Date:	1992
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/54674