Name
Abstract | ||
|---|---|---|
A random greedy algorithm, somewhat modifled, is analyzed by using a real time context and showing that the variables remain close to the solution of a natural difierential 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 lncD) of the vertices. Let H =( V;E )b e a( k+ 1)-uniform hypergraph on N vertices. A packing P is a family of disjoint edges. Given P we correspond the set S = V ¡ S P of those vertices v not in the packing, these v we call surviving vertices. We shall assume: † H is simple. That is, any two vertices are in at most one edge. † H is regular of degree D. That is, every vertex v lies in precisely De 2 E. We are interested in the asymptotics for k flxed, D;N !1 . We assume k ‚ 2i s fl xed throughout. We show Theorem. There exists a packing with jSj = O(ND¡1=k lncD) |
Year | Venue | Keywords |
|---|---|---|
1997 | Electr. J. Comb. | greedy algorithm,real time |
Field | DocType | Volume |
Adjacency matrix,Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Matrix (mathematics),Identity matrix,Mathematics | Journal | 4 |
Issue | Citations | PageRank |
2 | 0 | 0.34 |
References | Authors | |
4 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joel Spencer | 1 | 41 | 4.73 |