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

DOI10.15807/JORSJ.60.15zbMATH Open1371.90028OpenAlexW2583281281MaRDI QIDQ5267564FDOQ5267564

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

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

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)

Cited In (2)

• 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)