文章基本信息

标题：Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients
本地全文：下载
作者：Valentin E. Brimkov ; Stefan S. Dantchev
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper we study the Boolean Knapsack problem (KPR) aTx=1, x01n with real coefficients, in the framework of the Blum-Shub-Smale real number computational model \cite{BSS}. We obtain a new lower bound nlognf(1amin) for the time complexity of this problem, as well as an nlognf(bamin) lower time complexity bound for the classical Boolean Knapsack problem aTx=b, x01n with positive integer coefficients. Here n is the dimension of the problem, amin 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 (n2) which applies to both cases. We also construct certain algorithms for KPR. We suggest a way of defining the concept of a pseudopolynomial algorithm for KPR 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(n2) and O(n(amin)) , respectively, with each finding an approximation solution with an absolute error .