Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
Halman N. Theoretical Computer Science645 (C):41-47,2016.Type:Article
Date Reviewed: Jan 16 2017

The knapsack problem (KP) appears in many forms in science, economics, and engineering. The classical formulation uses a set of items, each with a weight and a value, and asks to determine the number of each item to include in a knapsack so that the total weight is less than or equal to its limit and the total revenue is as large as possible.

The formulation of KP considered by Halman, in this paper, is not considered the revenue optimization. More exactly, the author has obtained a deterministic fully polynomial-time approximation scheme for counting the number of integer knapsack solutions of the problem: “Given n elements with non-negative integer weights w =(w1, ..., wn), an integer capacity C and positive integer ranges u =(u1, ..., un), [...] find the number of distinct multisets whose weights add up to at most C.”

According to the author, the reported result is an improvement of n2 over the best-known deterministic algorithm proposed by Gopalan [1]. Halman has proved that the running time of the algorithm depends on n (cubic polynomial class), the logarithm of the sum of upper limits ui, and the reciprocal of the relative error.

The following concepts and tools were introduced in the second section to fulfill the aim of research: k-approximation sets and functions, and binding constraints based dynamic programming (DP) approaches (primal and dual). Two algorithms based on binding constraints are given: the first one, described in the second section, is based on the primal version of DP, while the second algorithm, developed and analyzed, in the third section is based on the dual version of DP. In the fourth section, the open problems are outlined.

The paper describes valuable results on the knapsack counting problem in a clear manner, with an excellent structure and relevant and recent references.

Reviewer:  G. Albeanu Review #: CR144999 (1705-0307)
1) Gopalan, P.; Klivans, A.; Meka, R.; Štefankovic, D.; Vigoda, E. An FPTAS for #Knapsack and related counting problems. In Proc. of FOCS. IEEE, 2011, 817–826.
Bookmark and Share
  Featured Reviewer  
 
Dynamic Programming (I.2.8 ... )
 
 
Deterministic (I.5.1 ... )
 
 
Approximation (G.1.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Dynamic Programming": Date
Optimum decision trees--an optimal variable theorem and its related applications
Miyakawa M. Acta Informatica 22(5): 475-498, 1985. Type: Article
Mar 1 1987
An efficient algorithm for optimal pruning of decision trees
Almuallim H. Artificial Intelligence 83(2): 347-362, 1996. Type: Article
Apr 1 1997
Visual unrolling of network evolution and the analysis of dynamic discourse
Brandes U., Corman S. Information Visualization 2(1): 40-50, 2003. Type: Article
Dec 30 2003
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy