Fast algorithms for knapsack via convolution and prediction

DOI10.1145/3188745.3188876zbMath1427.68376arXiv1811.12554OpenAlexW2808759691MaRDI QIDQ5230380

MohammadHossein Bateni, Saeed Seddighin, Mohammad Taghi 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

predictionconvolutionknapsack

Mathematics Subject Classification ID

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

Related Items (5)

Unnamed Item ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ ON BINARY SOLUTIONS TO SYSTEMS OF EQUATIONS ⋮ Unnamed Item ⋮ More on change-making and related problems

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