MINIMUM GENERALIZED 0-1 ASSIGNMENT

Next: MINIMUM QUADRATIC 0-1 ASSIGNMENT Up: Mathematical Programming Previous: MAXIMUM QUADRATIC PROGRAMMING Index

INSTANCE: Integer $m\times n$ -matrix $A\in Z^{m\cdot n}$ , integer m-vector $b\in Z^m$ , and binary $m\times n$ -matrix $C\in \{0,1\}^{m\cdot n}$ .
SOLUTION: A binary $m\times n$ -matrix $X\in \{0,1\}^{m\cdot n}$ such that there is exactly one 1 in each column of X, and $\displaystyle\sum\limits_{j=1}^{n} A_{i,j} X_{i,j}\le b_i$ for all $i\in [1..m]$ .
MEASURE: $\displaystyle\sum\limits_{i=1}^{m} \displaystyle\sum\limits_{j=1}^{n} C_{i,j} X_{i,j}$ .
Bad News: Not in APX [426].

Viggo Kann
2000-03-20