Is the following problem NP Complete?
We have $n$ variables $x_1$,$x_2$,....,$x_n$ and a set of constraints:
$sum_{i=a_1}^{b_1}x_i = h_1$
$sum_{i=a_2}^{b_2}x_i = h_2$
$sum_{i=a_3}^{b_3}x_i = h_3$
......
where $h_1$,$h_2$,...,$h_n$ are integers. We ask for an integer assignment of $x_1$,$x_2$,...,$x_n$.
The constraint matrix does not seem to be totally unimodular. Is the problem NP Complete?
No comments:
Post a Comment