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

DOI10.15807/JORSJ.60.15zbMath1371.90028OpenAlexW2583281281MaRDI QIDQ5267564

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

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

Related Items (2)

A note on submodular function minimization with covering type linear constraints ⋮ An approximation algorithm for the partial covering 0-1 integer program

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