A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH

DOI10.15807/JORSJ.60.15MaRDI QIDQ5267564zbMATH OpenOpenAlexFDO

Authors Yotaro Takazawa, Shinji Mizuno

Publication date 13 June 2017

Published in Journal of the Operations Research Society of Japan (Search for Journal in Brave)

Full work available at URL https://doi.org/10.15807/jorsj.60.15

zbMATH Keywords

combinatorial optimizationapproximation algorithmscovering integer programforcing graphminimum knapsack problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Integer programming (90C10) Transportation, logistics and supply chain management (90B06)

Recommendations

• Approximation of knapsack problems with conflict and forcing graphs
• Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
• Approximation algorithms for a two-phase knapsack problem
• An approximation algorithm for solving unconstrained two-dimensional knapsack problems
• Some thoughts on the 2-approximation algorithm for knapsack problems: a survey
• A minimal algorithm for the bounded knapsack problem
• A Minimal Algorithm for the Bounded Knapsack Problem
• On the approximability of the two-phase knapsack problem
• A new approximation algorithm for the knapsack problem
• An approximation scheme for the two-stage, two-dimensional knapsack problem

Cited in

(3)

• Approximation of knapsack problems with conflict and forcing graphs
• An approximation algorithm for the partial covering 0-1 integer program
• A note on submodular function minimization with covering type linear constraints

This page was built for publication: A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH

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