0-1 Knapsack in Nearly Quadratic Time

0-1 Knapsack in Nearly Quadratic Time

We study pseudo-polynomial time algorithms for the fundamental 0- 1 Knapsack problem. Recent research interest has focused on its finegrained complexity with respect to the number of items 𝑛 and the maximum item weight 𝑤max. Under (min, +)-convolution hypothesis, 0-1 Knapsack does not have𝑂( (𝑛+𝑤m...

Full description

Bibliographic Details
Main Author: Jin, Ce
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: Association for Computing Machinery STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing 2024
Online Access:https://hdl.handle.net/1721.1/155707

Internet

https://hdl.handle.net/1721.1/155707

Similar Items