Are there known algorithms for the following problem that beat the naive algorithm?

Input: A system $Ax \le b$ of $m$ linear inequalities.

Output: A feasible solution $x^*\in \{0,1 \}^n$ if one exists.

Assume that $A$ and $b$ have integer entries. I'm interested in worst-case bounds.


If $m$ is superlinear, such an algorithm would disprove the Strong Exponential Time Hypothesis, since formulas in conjunctive normal form are a special case of 0-1 programming and the Sparsification Lemma allows us to reduce $k$-SAT to CNF-SAT on linearly many clauses.

However, there is an algorithm due to Impagliazzo, Paturi, and myself that can solve such a system of inequalities if the number of wires, i.e. the number of nonzero coefficients in $A$ is linear. In particular, if the number of wires is $cn$, the algorithm runs in time $2^{(1-s)n}$, where $s=\frac1{c^{O(c^2)}}$.


If $m$ is small enough, you can do better than the naive algorithm, i.e., better than $2^n$ time. Here "small enough" means that $m$ is smaller than something like $n/\lg n$. The running time will still be exponential -- e.g., it might be $2^{n/2}$ time -- but it'll be faster than the naive algorithm.

Incidentally, it looks like this does allow us to solve the problem in faster than $2^n$ time for some cases where the matrix $A$ has a super-linear number of entries. I don't know how to square that with the other answer provided here. Consequently, you should check my answer carefully: it might indicate that I have made a serious mistake somewhere.

The basic approach: write $x=(x_0,x_1)$, where $x_0$ holds the first $n/2$ components of $x$ and $x_1$ holds the last $n/2$ components; and similarly $A=(A_0,A_1)$, where $A_0$ has the left $n/2$ columns of $A$ and $A_1$ the right $n/2$ columns. Now $Ax \le b$ can be re-written in the form

$$A_0 x_0 + A_1 x_1 \le b,$$

or equivalently,

$$A_0 x_0 \le b - A_1 x_1.$$

Enumerate all $2^{n/2}$ possibilities for $A_0 x_0$, and let $S$ denote the set of possible values, i.e.,

$$S=\{A_0 x_0 : x_0 \in \{0,1\}^{n/2}\}.$$

Similarly, enumerate the set $T$ of all $2^{n/2}$ possibilities for $b - A_1 x_1$, i.e.,

$$T = \{b - A_1 x_1 : x_1 \in \{0,1\}^{n/2}\}.$$

Now the problem becomes

Given sets $S,T \subseteq \mathbb{Z}^{m}$ of size $2^{n/2}$, does there exist $s\in S$ and $t \in T$ such that $s\le t$?

(Here $\le$ is taken pointwise, i.e., we require that $s_i \le t_i$ for all $i$.)

The latter problem is discussed on CS.StackExchange, and there is apparently an algorithm for it that runs in time $O(2^{n/2} (n/2)^{m-1})$. If $m$ is sufficiently small (say, smaller than $n/\lg n$), then it follows that the total running time will be less than $2^n$, as desired.

To help make this result sound more plausible, here's some very crude intuition. If we take the extreme case where $m=1$, of course this can be solved quickly. (There's actually a much simpler algorithm for the special case where $m=1$: let $x_i=1$ if $A_{1,i}\le 0$, otherwise $x_i=0$; now if any feasible solution exists, then this $x$ will be one.)

  • 1
    $\begingroup$ The algorithm from my answer also reduces to the vector problem described in your answer using the same method, i.e. split the variables and list all their assignments. $\endgroup$ Aug 30 '13 at 0:10
  • 2
    $\begingroup$ There are algorithms for the general integer programming problem whose running time has a $2^{O(m)}$ dependence on dimension, and polynomial dependence on everything else. See dl.acm.org/citation.cfm?id=380857. $\endgroup$ Aug 31 '13 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.