Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPLEXITY OVER THE REAL NUMBERS:
Reports tagged with Complexity over the Real Numbers:
TR98-015 | 16th January 1998
Valentin E. Brimkov, Stefan S. Dantchev

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

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

ISSN 1433-8092 | Imprint