Exact exponential-time algorithms for 0-1 programs with nonnegative data

Question

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

Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers.

Output: an optimal solution $x^*$ to $\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}$.

This question is a refined version of my previous question Exact exponential-time algorithms for 0-1 programming.

Answer 1

if the number of non-zero coefficients in $A$ is linear in $n,ドル there is an algorithm that solves this problem in less than 2ドル^n$ time.

Here's how it works. We use the standard connection between an optimization problem and its corresponding decision problem. To test whether there exists a solution $x$ where $Ax\le b$ and $c^T x \ge \alpha,ドル we will form a decision problem: we will adjoin the constraint $c^T x\ge \alpha$ to the matrix $A,ドル and test whether there exists any $x$ such that $Ax \le b$ and $-c^T x \le -\alpha$. In particular, we will form a new matrix $A'$ by taking $A$ and adding an extra row containing $-c^T,ドル and we will form $b'$ by taking $b$ and adjoining an extra row with $-\alpha$. We obtain a decision problem: does there exist $x \in \{0,1\}^n$ such that $A' x \le b'$? The answer to this decision problem tells us whether there exists a solution to the original optimization problem of value $\alpha$ or greater. Moreover, as explained in the answer to your prior question, this decision problem can be solved in less than 2ドル^n$ time, if the number of non-zero coefficients in $A'$ is linear in $n$ (and thus if the number of non-zero coefficients in $A$ is linear in $n$). Now we can use binary search on $\alpha$ to solve your optimization problem in less than 2ドル^n$ time.

My thanks to AustinBuchanan and Stefan Schneider for helping to debug an earlier version of this answer.

• Austin Buchanan: Can you give a stronger answer: such as "there is a time $O(2^{n/2})$ algorithm" or "an algorithm faster than $O(2^n)$ would disprove ..."?
• D.W.: @AustinBuchanan, if the number of dimensions of $b$ is small enough, there is an $O^*(2^{n/2})$ algorithm, as documented in my answer to the other question. That's the best that I know how to do; I don't know how to do any better than that. Maybe others will be able to provide a stronger answer!
• Austin Buchanan: $O^*(2^{n/2})$ time holds whenever the number of constraints is $O(1)$?

Answer 2

If we consider the minimization problem $\min_y \{c^T y : Ay \ge b, y \in \{ 0,1\}^n \},ドル then the following reduction shows that an algorithm running in time $O(2^{\delta n/2})$ for $\delta <1$ would disprove the SETH. A reformulation proves the same result for the intended problem (the maximization version).

Given an instance $\Phi = \wedge_{i=1}^m C_i$ of CNF-SAT with variables $\{x_j \}_{j=1}^n,ドル formulate a 0-1 IP with two variables $y_j, \overline{y}_j$ for each variable $x_j$ in the SAT instance. As usual, the clause $(x_1 \vee \overline{x}_2 \vee x_3)$ would be represented as $y_1 + \overline{y}_2 + y_3 \ge 1$. Then for every variable $x_j$ in the SAT instance, add a constraint $y_j + \overline{y}_j \ge 1$. The objective is to minimize $\sum_{j=1}^n (y_j + \overline{y}_j)$. The objective of the IP will be $n$ iff the SAT instance is satisfiable.

Thanks to Stefan Schneider for the correction.

Update: in On Problems as Hard as CNF-Sat the authors conjecture that SET COVER cannot be solved in time $O(2^{\delta n}),ドル $\delta <1,ドル where $n$ refers to the number of sets. If true, this would show that my problem cannot be solved in time $O(2^{\delta n})$ as well.

Update 2. As far as I can tell, assuming SETH, my problem cannot be solved in time $O(2^{\delta n}),ドル since it has been shown that Hitting Set (with a ground set of size $n$) cannot be solved in time $O(2^{\delta n})$.

• Stefan Schneider: Since you double the number of variables, I think this only shows that an algorithm for this problem with runtime $O(2^{\delta n/2})$ would contradict SETH.
• Austin Buchanan: Wait...the authors from On Problems as Hard as CNF-SAT state that "for every $\epsilon <1,ドル an $O(2^{\epsilon n})$ algorithm for Hitting Set $\dots$ would violate SETH." Doesn't this work?