MAXIMUM WEIGHTED SATISFIABILITY WITH BOUND

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

INSTANCE: Set U of variables, boolean expression F over U, a nonnegative bound $B\in N$ , for each variable $u\in U$ a weight $w(u)\in N$ such that $B\le\sum\limits_{u\in U} w(u)\le 2\,B$ .
SOLUTION: A truth assignment for U, i.e., a subset $U'\subseteq U$ such that the variables in U' are set to true and the variables in U-U' are set to false.
MEASURE: $\displaystyle\sum\limits_{v\in U'} w(v)$ if the truth assignment satisfies the boolean expression F and B otherwise.
Good News: Approximable within 2 [126].
Bad News: APX-complete [126].
Comment: Variation in which $\sum_{u\in U} w(u)\le \left(1+1/(\vert U\vert-1)\right)\,B$ is PTAS-complete [126].

Viggo Kann
2000-03-20