LO6 M AXIMUM D ISTINGUISHED O NES

     
• I NSTANCE : Disjoint sets X,Z of variables, collection C of disjunctive clauses of at most 3 literals, where a literal is a variable or a negated variable in .
• S OLUTION : Truth assignment for X and Z that satisfies every clause in C .
• M EASURE : The number of Z variables that are set to true in the assignment.

• Bad News: NPO PB-complete [ 200 ].
• Comment: Transformation from M AXIMUM N UMBER OF S ATISFIABLE F ORMULAS [ 281 ]. Not approximable within for any [ 197 ]. M AXIMUM O NES , the variation in which all variables are distinguished, i.e. , is also NPO PB-complete [ 200 ], and is not approximable within for any [ 197 ].   M AXIMUM W EIGHTED S ATISFIABILITY , the weighted version, in which every variable is assigned a nonnegative weight, is NPO-complete [ 28 ].