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

DOI10.1016/J.DAM.2017.08.024MaRDI QIDQ2297657zbMATH OpenOpenAlexFDO

Authors Yotaro Takazawa, Shinji Mizuno, Tomonari Kitahara

Publication date 20 February 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2017.08.024

zbMATH Keywords

approximation algorithmsprimal-dual methodpartial covering 0-1 integer program

Mathematics Subject Classification ID

Integer programming (90C10) Boolean programming (90C09)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1305393 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH
• Approximation algorithm for partial positive influence problem in social network
• Approximation algorithms for partial covering problems
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• Local ratio method on partial set multi-cover
• On combinatorial approximation of covering 0-1 integer programs and partial set cover
• Primal-dual schema for capacitated covering problems

Cited in

(9)

• An improved approximation algorithm for the partial Latin square extension problem.
• scientific article; zbMATH DE number 4068611 (Why is no real title available?)
• scientific article; zbMATH DE number 1754596 (Why is no real title available?)
• On combinatorial approximation of covering 0-1 integer programs and partial set cover
• Approximation algorithms for the covering-type \(k\)-violation linear program
• An improved approximation algorithm for the covering 0-1 integer program
• On column-restricted and priority covering integer programs
• Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
• One for the price of two: a unified approach for approximating covering problems

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

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