Random Independence Systems
John H. Reif, Paul G. Spirakis · 1981
This report introduces a new random structure generalizing matroids. These random independence systems allow us to develop general techniques for solving hard combinatorial optimization problems with random inputs.