An improved approximation algorithm for the covering 0-1 integer program

MaRDI QIDQ4963655zbMATH OpenFDO

Authors Yotaro Takazawa, Shinji Mizuno, Tomonari Kitahara

Publication date 19 February 2021

Full work available at URL http://yokohamapublishers.jp/online-p/PJO/vol15/pjov15n2p195.pdf

zbMATH Keywords

approximation algorithmsprimal-dual methodcovering integer program

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for covering/packing integer programs
• On combinatorial approximation of covering 0-1 integer programs and partial set cover
• An approximation algorithm for the partial covering 0-1 integer program
• Approximating sparse covering integer programs online
• On approximating (sparse) covering integer programs

Cited in

(7)

• An approximation algorithm for the partial covering 0-1 integer program
• Approximating covering integer programs with multiplicity constraints
• Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
• Approximation algorithms for covering/packing integer programs
• Monotone covering problems with an additional covering constraint
• On combinatorial approximation of covering 0-1 integer programs and partial set cover
• On a geometric graph-covering problem related to optimal safety-landing-site location

This page was built for publication: An improved approximation algorithm for the covering 0-1 integer program

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