質問

I've come across this problem while trying to work out a table-formatting algorithm.

It's very similar to standard linear programming (though it uses $>$ instead of $<$; I'm not extremely familiar with linear programming, but I believe this doesn't matter much).

Let $\vec v = (v_1, \dots, v_n)$ be a vector of positive-integer variables.

The problem is to find if there is an assignment to $\vec v$ such that

$$ v_1 + \dots + v_n = c $$

and

$$ A \vec v \geq \vec w $$

where $c$ is a known constant, $\vec w$ is a known constant, and $A$ is a matrix with the special property that each row of $A$ is of the form $(0, \dots, 0, 1, \dots, 1, 0, \dots, 0)$.

That is, each inequality constraint only uses coefficients 1 and 0, and only "consecutive" variables appear in each linear constraint.


I think that this problem is NP-complete, but I haven't been able to prove it.

I think a reduction to exactly-1-in-3-SAT or set-cover is most likely to succeed (variables would be literals/values respectively and rows in the matrix would correspond to clauses/sets), but the restriction that constraints only refer to consecutive variables doesn't seem strong enough to describe arbitrary clauses/sets.

Alternatively, I might be wrong, and this problem actually has an algorithm that I have been missing. (The problem I'm actually interested in solving is finding the smallest $c$ such that constraints remain satisfiable, but I've phrased the problem this way so that it remains a simple decision problem)


As an example, here's a small instance of this problem:

$$ \begin{array}{} v_1 + v_2 + v_3 + v_4&=& 10 \\ v_1 &\geq& 1 \\ v_2 &\geq& 1 \\ v_2 + v_3 &\geq & 3 \\ v_3 + v_4 & \geq & 4 \\ v_3 &\geq& 1 \\ v_4 &\geq& 1 \end{array} $$

which has a possible assignment $\vec v = (1, 1, 6, 2) $.

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top