Probabilistic Analysis of Random Extension-Rotation Algorithms

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1981
Accession Number
ADA109035

Entities

People

  • John Reif
  • Paul G. Spirakis

Organizations

  • Harvard University

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • California
  • Computations
  • Heuristic Methods
  • Intervals
  • Markov Processes
  • Mathematical Analysis
  • Mathematics
  • New York
  • Numbers
  • Optimization
  • Probability
  • Probability Density Functions
  • Random Variables
  • Rotation
  • Stochastic Processes

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Statistical inference.