Sub-Exponential Algorithms for 0/1 Knapsack and Bin Packing

摘要

This paper presents simple algorithms for 0/1 Knapsack and Bin Packing with a fixed number of bins that achieve time complexity p(n)·2~(o({the square root of}x)) where x is the total bit length of a list of sizes for n objects. The algorithms are adaptations of a method that achieves a similar complexity for the Partition and Subset Sum problems. The method is shown to be general enough to be applied to other optimization or decision problem based on a list of numeric sizes or weights. This establishes that 0/1 Knapsack and Bin Packing have sub-exponential time complexity using input length as the complexity parameter. It also supports the expectation that all NP-complete problems with pseudo-polynomial time algorithms can be solved deterministically in sub-exponential time.