MAXIMUM DISTINGUISHED ONES

• INSTANCE: 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 $X\cup Z$.

• SOLUTION: Truth assignment for X and Z that satisfies every clause in C.

• MEASURE: The number of Z variables that are set to true in the assignment.

  
  

• Bad News: NPO PB-complete [282].

• Comment: Transformation from MAXIMUM NUMBER OF SATISFIABLE FORMULAS [389]. Not approximable within $(\vert X\vert+\vert Z\vert)^{1-\varepsilon }$ for any $\varepsilon >0$ [279]. MAXIMUM ONES, the variation in which all variables are distinguished, i.e. $\vert X\vert=\emptyset$, is also NPO PB-complete [282], and is not approximable within $\vert Z\vert^{1-\varepsilon }$ for any $\varepsilon >0$ [279]. MAXIMUM WEIGHTED SATISFIABILITY, the weighted version, in which every variable is assigned a nonnegative weight, is NPO-complete [47].