<p>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 &lt;1$ would disprove the SETH. A reformulation proves the same result for the intended problem (the maximization version).</p>

<p>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. </p>

<p>Thanks to Stefan Schneider for the correction.</p>

<p>Update: in <a href="http://www.ii.uib.no/~daniello/papers/seth.pdf" rel="nofollow">On Problems as Hard as CNF-Sat</a> the authors conjecture that SET COVER cannot be solved in time $O(2^{\delta n})$, $\delta &lt;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.</p>

<p>Update 2. As far as I can tell, assuming SETH, my problem cannot be solved in time $O(2^{\delta n})$, since it <a href="http://arxiv.org/abs/1112.2275" rel="nofollow">has been shown</a> that Hitting Set (with a ground set of size $n$) cannot be solved in time $O(2^{\delta n})$.</p>

CC BY-SA 3.0
2013-09-01T21:20:21.760Z
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.
Stefan Schneider
CC BY-SA 3.0
2013-09-16T22:50:09.163Z
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?
Austin Buchanan
CC BY-SA 3.0
2013-09-01T19:55:25.313Z
2013-12-16T22:06:42.200Z
2013-12-16T22:06:42.200Z
Austin Buchanan
<p>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.</p>

<p>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 <a href="https://cstheory.stackexchange.com/a/18483/5038">the answer to your prior question</a>, 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.</p>

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

CC BY-SA 3.0
2013-08-25T19:07:55.163Z
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 ..."?
Austin Buchanan
CC BY-SA 3.0
2013-08-30T01:52:25.717Z
@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](http://cstheory.stackexchange.com/a/18799/5038).  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!
D.W.
CC BY-SA 3.0
2013-08-30T15:36:44.553Z
$O^*(2^{n/2})$ time holds whenever the number of constraints is $O(1)$?
Austin Buchanan
CC BY-SA 3.0
2013-08-25T18:57:00.623Z
2013-08-26T01:31:10.937Z
2017-04-13T12:32:28.080Z
D.W.
<p>Are there known algorithms for the following problem that beat the naive algorithm?</p>
<blockquote>
<p>Input: matrix <span class="math-container">$A$</span> and vectors <span class="math-container">$b,c$</span>, where all entries of <span class="math-container">$A,b,c$</span> are nonnegative integers.</p>
<p>Output: an optimal solution <span class="math-container">$x^*$</span> to <span class="math-container">$\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}$</span>.</p>
</blockquote>
<p>This question is a refined version of my previous question <a href="https://cstheory.stackexchange.com/questions/18482/exact-exponential-time-algorithms-for-0-1-programming">Exact exponential-time algorithms for 0-1 programming</a>.</p>

<np-hardness><integer-programming><exp-time-algorithms>
Exact exponential-time algorithms for 0-1 programs with nonnegative data
Austin Buchanan
# Exact exponential-time algorithms for 0-1 programs with nonnegative data

(Asked by: username_0 on 2013-08-24)

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](https://cstheory.stackexchange.com/questions/18482/exact-exponential-time-algorithms-for-0-1-programming).

**Tags:** np-hardness, integer-programming, exp-time-algorithms

---

## 2 answers

### Answer by username_2 on 2013-08-25. Score: 5

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](https://cstheory.stackexchange.com/a/18483/5038), 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.

> **Comments:**
> **username_0**: 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 ..."?  
> **username_2**: @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](http://cstheory.stackexchange.com/a/18799/5038).  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!  
> **username_0**: $O^*(2^{n/2})$ time holds whenever the number of constraints is $O(1)$?  

---

### Answer by username_0 on 2013-09-01. Score: 4

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](http://www.ii.uib.no/~daniello/papers/seth.pdf) 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](http://arxiv.org/abs/1112.2275) that Hitting Set (with a ground set of size $n$) cannot be solved in time $O(2^{\delta n})$.

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  

---

