A Polynomial Algorithm for Partitioning Problems

作者：Tahaee Seyed Abdoreza^*; Jahangir Amir Hossein

来源：ACM Transactions on Embedded Computing Systems, 2010, 9(4): 34.

DOI：10.1145/1721695.1721700

• Algorithms
• Design
• Partitioning problem
• hardware/software codesign
• maximum flow minimum cut problem
• NP-hard problems

This article takes a theoretical approach to focus on the algorithmic properties of hardware/software partitioning. It proposes a method with polynomial complexity to find the global optimum of an NP-hard model partitioning problem for 75% of occurrences under some practical conditions. The global optimum is approached with a lower bound distance for the remaining 25%. Furthermore, this approach ensures finding the 2-approximate of the global optimum partition in 97% of instances where technical assumptions exist. The strategy is based on intelligently changing the parameters of the polynomial model of the partitioning problem to force it to produce (or approach) the exact solution to the NP-hard model.

• 出版日期2010-3