Probability-boosting technique for combinatorial optimization.

In many combinatorial optimization problems we want a particular set of k out of n items with some certain properties (or constraints). These properties may involve the k items. In the worst case a deterministic algorithm must scan n-k items in the set to verify the k items.