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.


Full Text: PDF