MP1 M INIMUM 0-1 P ROGRAMMING

     
• I NSTANCE : Integer -matrix , integer m -vector , nonnegative integer n -vector .
• S OLUTION : A binary n -vector such that .
• M EASURE : The scalar product of c and x , i.e., .

• Bad News: NPO-complete [ 280 ].
• Comment: Transformation from M INIMUM W EIGHTED S ATISFIABILITY . Variation in which for all i is NPO PB-complete and not approximable within for any [ 202 ]. Variation in which there are at most k non-zero entries on each row of the matrix with k constant is approximable within k [ 147 ] and [ 171 ].
• Garey and Johnson: MP1