On polynomial complexity of a stochastic algorithm for mixed zero-one programs

✍ Scribed by Raj Jagannathan

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 236 KB
• Volume: 134
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00301-9

✦ Synopsis

A stochastic (randomization) algorithm for solving mixed zero-one programs in a yes-no 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 classiÿed 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.