Skip to main content
1 of 4
Austin Buchanan
  • 1.2k
  • 1
  • 17
  • 28

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

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.

Austin Buchanan
  • 1.2k
  • 1
  • 17
  • 28