Real Time Asymptotic Packing

  • Joel Spencer

Abstract

A random greedy algorithm, somewhat modified, is analyzed by using a real time context and showing that the variables remain close to the solution of a natural differential equation. Given a $(k+1)$-uniform simple hypergraph on $N$ vertices, regular of degree $D$, the algorithm gives a packing of disjoint hyperedges containing all but $O(ND^{-1/k}\ln^cD)$ of the vertices.

Published
1996-06-12