ECCC-Report TR98-015https://eccc.weizmann.ac.il/report/1998/015Comments and Revisions published for TR98-015en-usFri, 13 Mar 1998 17:47:38 +0200
Paper TR98-015
| Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients |
Valentin E. Brimkov,
Stefan S. Dantchev
https://eccc.weizmann.ac.il/report/1998/015In 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$.
Fri, 13 Mar 1998 17:47:38 +0200https://eccc.weizmann.ac.il/report/1998/015