Publications [#290778] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Spirakis, PG, Random matroids, Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 1980-April (April, 1980), pp. 385-397, ACM Press, ISSN 0737-8017 (Revised as Harvard University TR-28-81, Probabilistic Analysis of Random Extension-Rotation Algorithms.) [pdf], [doi]
   (last updated on 2026/01/14)

   Abstract:
   We introduce a new random structure generalizing matroids. These random matroids allow us to develop general techniques for solving hard combinatorial optimization problems with random inputs.