Constant-time approximation algorithms for the knapsack problem

DOI10.1007/978-3-642-29952-0_17zbMATH Open1354.68299OpenAlexW329165401MaRDI QIDQ2898024FDOQ2898024

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

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

Mathematics Subject Classification ID

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

Cited In (10)

• A linear-time algorithm for solving continuous maximin knapsack problems
• The online knapsack problem with incremental capacity
• Title not available (Why is that?)
• Randomized algorithms for online knapsack problems
• A sublinear-time approximation scheme for bin packing
• A PTAS for the time-invariant incremental knapsack problem
• Approximating the 3-period incremental knapsack problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• On approximating the incremental 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)