Linear Time Algorithms for Knapsack Problems with Bounded Weights
From MaRDI portal
Publication:4939603
DOI10.1006/jagm.1999.1034zbMath0951.90047OpenAlexW2076844787WikidataQ58826506 ScholiaQ58826506MaRDI QIDQ4939603
Publication date: 6 February 2000
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1999.1034
Related Items
Scheduling lower bounds via AND subset sum ⋮ New exact approaches and approximation results for the penalized knapsack problem ⋮ Approximating subset sum ratio via subset sum computations ⋮ A new fully polynomial time approximation scheme for the interval subset sum problem ⋮ Change-making problems revisited: a parameterized point of view ⋮ Learning-augmented algorithms for online subset sum ⋮ Algebraic algorithms for variants of subset sum ⋮ Faster algorithms for \(k\)-\textsc{Subset Sum} and variations ⋮ An efficient fully polynomial approximation scheme for the Subset-Sum problem. ⋮ An exact approach for the bilevel knapsack problem with interdiction constraints and extensions ⋮ Unnamed Item ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ Worst-case analysis of the subset sum algorithm for bin packing. ⋮ Selfish bin covering ⋮ Three is easy, two is hard: Open shop sum-batch scheduling problem refined ⋮ Efficient algorithms for real-life instances of the variable size bin packing problem ⋮ A Decentralized Heuristic for Multiple-Choice Combinatorial Optimization Problems ⋮ Where are the hard knapsack problems? ⋮ Unnamed Item ⋮ Structural parameterizations of budgeted graph coloring ⋮ More on change-making and related problems ⋮ Faster Pseudopolynomial Time Algorithms for Subset Sum ⋮ Actively secure setup for SPDZ ⋮ New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems ⋮ Target-based computer-assisted orchestration: complexity and approximation algorithms ⋮ Modified subset sum heuristics for bin packing ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction* ⋮ Faster algorithms for \(k\)-subset sum and variations
Uses Software