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...
| Main Author: | |
|---|---|
| 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 |