Accession Number:

ADA109035

Title:

Probabilistic Analysis of Random Extension-Rotation Algorithms

Descriptive Note:

Technical rept.

Corporate Author:

HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB

Personal Author(s):

Report Date:

1981-10-01

Pagination or Media Count:

56.0

Abstract:

We introduce a new random structure generalizing matroids. The random independence systems RIS allow us to develop general techniques for solving hard combinatorial optimization problems with random inputs. We describe a randomized algorithm for efficiently constructing an independent set of fixed size in an instance of a random independence system. We provide a general method of analysis of the performance of this algorithm, which allows us to derive bounds on the mean, variance and all the moments of the time complexity of the algorithm. Author

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE