The Worst and the Most Probable Performance of a Class of Set-Covering Algorithms
Vladimir Lifschitz, Boris G. Pittel · SIAM Journal on Computing · 1983
Let $I = (1, \cdots ,m),\, J = (1, \cdots ,n)$ and $\Delta = (D_i )_{i \in I} $ be a family of subsets $D_i $ of J. A class of algorithms which find a minimum number of $D_i $’s covering $D = \cup _{i \in I} D_i $ is studied. A measure $T(\Delta )$ of the computation time is shown to grow exponentially with the size of the problem in the worst case, namely $\max _\Delta T(\Delta ) > (4^{1/5} )^{\min (m,n')} > 1.319^{\min (m,n')} ,\, n' = |D|$. For $m = n'$ and a large subclass of algorithms, an estimate $\max _\Delta T(\Delta ) < (3/4^{1/3} )^m < (1.890)^m $ is established, so they always perform better than the obvious trivial procedure. Let, on the other hand, be chosen at random. Under condition in $\ln n/\ln m \to \gamma \in (0,\infty )$, it is proven that \[ P\left(m^{c_1 (\gamma )\ln m} \leqq T(\Delta ) \leqq m^{c_2 (\gamma )\ln m} \right) \to 1. \] Hence, asymptotically almost certainly, the computation time is of a considerably lower order than that in Hence, asymptotically almost certainly, the computation time is of a considerably lower order than that in the worst case, but it is still far from being polynomially bounded.