The random greedy algorithm conjecture for covering designs
The random greedy algorithm conjecture for covering designs
Let and be fixed, and let . Consider a covering produced by the random greedy algorithm, and define its density as the number of blocks divided by the asymptotically optimal number of blocks. Random greedy covering conjecture. The expected density of a covering produced by the random greedy algorithm is
This conjecture is suggested by empirical log-log plots and numerical estimates for several fixed pairs ; the supplied text gives no resolution, so its status remains open.
Sources & referencesView supporting material
Primary source
Daniel Gordon, Greg Kuperberg, Oren Patashnik and Joel Spencer, “Asymptotically optimal covering designs”, arXiv:math/9511224 (1995).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.