MAXIMUM CONSTRAINED PARTITION

• INSTANCE: Finite set A and a size $s(a)\in Z^+$ for each $a\in A$, element $a_0\in A$, and a subset $S\subseteq A$.
• SOLUTION: A partition of A, i.e., a subset $A'\subseteq A$ such that $\sum_{a\in A'} s(a)=\sum_{a\in A-A'} s(a)$.
• MEASURE: Number of elements from S on the same side of the partition as $a_0$.

  
  

• Bad News: Not approximable within $\vert A\vert^{\varepsilon }$ for some $\varepsilon >0$ [476].
• Garey and Johnson: Similar to SP12