Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Fast multidimension multichoice knapsack heuristic for MP-SoC runtime management
Ykman-Couvreur C., Nollet V., Catthoor F., Corporaal H. ACM Transactions on Embedded Computing Systems10 (3):1-16,2011.Type:Article
Date Reviewed: Jul 1 2011

Knapsack problems are among the most intensely studied problems in combinatorial optimization. In this paper, Ykman-Couvreur et al. present “a new fast and lightweight heuristic for finding near-optimal solutions for [multidimension multichoice knapsack problems (MMKPs)].” The MMKP is a combination of the multidimension knapsack problem (where several resources are present, but only one set) and the multichoice knapsack problem (where several sets exist, but only one resource). Within this framework, the authors introduce a multiprocessor system-on-chip (MP-SoC) heuristic suitable for multiprocessor platforms, which they then challenge on both solution quality and performance, compared with the state-of-the-art heuristics.

Although the discussed issue is very complex, the authors manage to find an optimal balance between a comprehensive presentation, in terms of a consistent thread and useful illustrations, and high mathematical accuracy. However, while this paper targets specialists in this area with an interest in efficient algorithms for solving MMKPs, it fails to attract mathematicians in other disciplines.

Based on the remarkable advantages of the presented study, the paper is recommended to readers with further applications in mind.

Reviewer:  Hamid R. Noori Review #: CR139198 (1112-1310)
Bookmark and Share
  Featured Reviewer  
 
Applications (G.2.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Applications": Date
Inf-semilattice approach to self-dual morphology
Heijmans H., Keshet (Kresch) R. Journal of Mathematical Imaging and Vision 17(1): 55-80, 2002. Type: Article
Jul 21 2003
 Engineering graph clustering: models and experimental evaluation
Brandes U., Gaertler M., Wagner D. Journal of Experimental Algorithmics 121.1-es, 2007. Type: Article
Sep 27 2007

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