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 lnc D) of the vertices.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1-11 |
| Number of pages | 11 |
| Journal | Electronic Journal of Combinatorics |
| Volume | 4 |
| Issue number | 2 R |
| State | Published - 1997 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics