Fast algorithms for knapsack via convolution and prediction

DOI10.1145/3188745.3188876MaRDI QIDQ5230380zbMATH OpenOpenAlexFDO

Authors MohammadHossein Bateni, S. Seddighin, Mohammad T. Hajiaghayi, Clifford Stein

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.12554

zbMATH Keywords

convolutionknapsackprediction

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Dynamic programming (90C39)

Abstract: The Problem{knapsack} problem is a fundamental problem in combinatorial optimization. It has been studied extensively from theoretical as well as practical perspectives as it is one of the most well-known NP-hard problems. The goal is to pack a knapsack of size $t$ with the maximum value from a collection of $n$ items with given sizes and values. Recent evidence suggests that a classic $O(nt)$ dynamic-programming solution for the Problem{knapsack} problem might be the fastest in the worst case. In fact, solving the Problem{knapsack} problem was shown to be computationally equivalent to the Problem{$(min,+)$ convolution} problem, which is thought to be facing a quadratic-time barrier. This hardness is in contrast to the more famous Problem{$(+,cdot)$ convolution} (generally known as Problem{polynomial multiplication}), that has an $O(nlogn)$-time solution via Fast Fourier Transform. Our main results are algorithms with near-linear running times (in terms of the size of the knapsack and the number of items) for the Problem{knapsack} problem, if either the values or sizes of items are small integers. More specifically, if item sizes are integers bounded by $smax$, the running time of our algorithm is $ildeO((n+t)smax)$. If the item values are integers bounded by $vmax$, our algorithm runs in time $ildeO(n+tvmax)$. Best previously known running times were $O(nt)$, $O(n^{2}smax)$ and $O(nsmaxvmax)$ (Pisinger, J. of Alg., 1999).

Recommendations

• Constant-time approximation algorithms for the knapsack problem
• Dynamic programming revisited: Improving knapsack algorithms
• A faster FPTAS for knapsack problem with cardinality constraint
• On Problems Equivalent to (min,+)-Convolution

Cited in

(13)

• More on change-making and related problems
• High generalization performance structured self-attention model for knapsack problem
• Capacitated dynamic programming: faster knapsack and graph algorithms
• On binary solutions to systems of equations
• scientific article; zbMATH DE number 7651168 (Why is no real title available?)
• Structured ( ,+)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
• No polynomial kernels for knapsack
• Minimizing tardy processing time on a single machine in near-linear time
• Minimizing tardy processing time on a single machine in near-linear time
• Fast convolutions for near-convex sequences
• Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
• Knapsack and subset sum with small items
• Even faster knapsack via rectangular monotone min-plus convolution and balancing

This page was built for publication: Fast algorithms for knapsack via convolution and prediction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230380)