The random greedy algorithm conjecture for covering designs

Let kk and tt be fixed, and let D=(kt)1D=\binom{k}{t}-1. 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

1+Θ(v(kt)/D).1+\Theta\bigl(v^{-(k-t)/D}\bigr).

This conjecture is suggested by empirical log-log plots and numerical estimates for several fixed pairs (k,t)(k,t); 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.