9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ..."? $\endgroup$ – Austin Buchanan Aug 25 '13 at 19:07
  • $\begingroup$ @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! $\endgroup$ – D.W. Aug 30 '13 at 1:52
  • $\begingroup$ $O^*(2^{n/2})$ time holds whenever the number of constraints is $O(1)$? $\endgroup$ – Austin Buchanan Aug 30 '13 at 15:36
4
$\begingroup$

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})$.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Stefan Schneider Sep 1 '13 at 21:20
  • $\begingroup$ 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? $\endgroup$ – Austin Buchanan Sep 16 '13 at 22:50

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.