Constant-time approximation algorithms for the knapsack problem

DOI10.1007/978-3-642-29952-0_17MaRDI QIDQ2898024zbMATH OpenOpenAlexFDO

Authors Hiro Ito, Susumu Kiyoshima, Yuichi Yoshida

Publication date 16 July 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-29952-0_17

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 7122316
• Hardness of approximation for knapsack problems
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• A sublinear-time approximation scheme for bin packing
• A subquadratic approximation scheme for partition

Cited in

(14)

• A linear-time algorithm for solving continuous maximin knapsack problems
• The online knapsack problem with incremental capacity
• scientific article; zbMATH DE number 1408349 (Why is no real title available?)
• Randomized algorithms for online knapsack problems
• Fast algorithms for knapsack via convolution and prediction
• A sublinear-time approximation scheme for bin packing
• Hardness of approximation for knapsack problems
• A PTAS for the time-invariant incremental knapsack problem
• Approximating the 3-period incremental knapsack problem
• A subquadratic approximation scheme for partition
• Approximation algorithms for knapsack problems with cardinality constraints
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• On approximating the incremental knapsack problem
• Approximation algorithms for the weight-reducible knapsack problem

This page was built for publication: Constant-time approximation algorithms for the knapsack problem

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