On polynomial complexity of a stochastic algorithm for mixed zero-one programs
A stochastic (randomization) algorithm for solving mixed zero-one programs in a yesno form is presented. Under a set of conditions, we show that any mixed zero-one program is such that either a feasible solution for the problem is obtained or it is classified as infeasible. The algorithm is such that its random running time has its kth moment, k=1,,j, for any j, bounded by a polynomial in n, the number of zero-one variables.
mixed zero-one program randomization method polynomial time probabilistic analysis central limit theorem