Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-015 | 16th January 1998 00:00

Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients


Authors: Valentin E. Brimkov, Stefan S. Dantchev
Publication: 13th March 1998 17:47
Downloads: 1386


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

ISSN 1433-8092 | Imprint