TR98-015 Authors: Valentin E. Brimkov, Stefan S. Dantchev

Publication: 13th March 1998 17:47

Downloads: 2451

Keywords:

In this paper we study the Boolean Knapsack problem (KP$_{{\bf R}}$)

$a^Tx=1$, $x \in \{0,1\}^n$ with real coefficients, in the framework

of the Blum-Shub-Smale real number computational model \cite{BSS}.

We obtain a new lower bound

$\Omega \left( n\log n\right) \cdot f(1/a_{\min})$ for the time

complexity of this problem, as well as an

$\Omega \left( n\log n\right) \cdot f(b/a_{\min})$ lower time

complexity bound for the classical Boolean Knapsack problem $a^Tx=b$, $x \in \{0,1\}^n$

with positive integer coefficients. Here $n$ is the dimension of

the problem, $a_{\min }$ is the minimal coefficient in the input,

and $f$ is any continuous function of one variable.

These lower bounds appear as alternatives to the well known lower

bound $\Omega (n^2)$ which applies to both cases.

We also construct certain algorithms for KP$_{{\bf R}}$. We suggest

a way of defining the concept of a pseudopolynomial algorithm for

KP$_{{\bf R}}$ and design such an algorithm. On integer inputs

this algorithm is pseudopolynomial according to the classical

complexity theory. Overall, it is seen as superior to the

classical dynamic programming algorithm. Finally, we present two

algorithms with running times $O(n^2/\varepsilon )$ and

$O(n/(\varepsilon a_{\min }))$, respectively, with each finding an

approximation solution with an absolute error $\varepsilon$.