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: | Jin, Ce |
---|---|
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 |
Similar Items
-
An Accelerated Fixed-Point Algorithm Applied to Quadratic Convex Separable Knapsack Problems
by: Atécio Alves, et al.
Published: (2024-01-01) -
Method for the solution of the multi-dimensional 0/1 knapsack problem
by: Weingartner, H. Martin.
Published: (2009) -
An efficient optimizer for the 0/1 knapsack problem using group counseling
by: Yazeed Yasin Ghadi, et al.
Published: (2023-04-01) -
Binary salp swarm algorithm for discounted {0-1} knapsack problem.
by: Binh Thanh Dang, et al.
Published: (2022-01-01) -
Penerapan algoritma genetik untuk menyelesaikan masalah Knapsack 0-1
by: , INDRIANINGSIH, Yuliani, et al.
Published: (2002)