Next: MAXIMUM NUMBER OF SATISFIABLE Up: Propositional Logic Previous: MINIMUM DISTINGUISHED ONES Index

### MAXIMUM WEIGHTED SATISFIABILITY WITH BOUND

- INSTANCE: Set U of variables, boolean expression F over U, a nonnegative bound , for each variable a weight such that .

- SOLUTION: A truth assignment for U, i.e., a subset such that the variables in U' are set to true and the variables in U-U' are set to false.

- MEASURE: if the truth assignment satisfies the boolean expression F and B otherwise.

- Good News: Approximable within 2 [118].

- Bad News: APX-complete [118].

- Comment: Variation in which is PTAS-complete [118].