Approximation algorithms for the covering-type k-violation linear program

DOI10.1007/S11590-019-01425-WMaRDI QIDQ2329669zbMATH OpenOpenAlexFDO

Authors Yotaro Takazawa, Shinji Mizuno, Tomonari Kitahara

Publication date 18 October 2019

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-019-01425-w

zbMATH Keywords

\(k\)-violation linear programapproximation algorithmslinear relaxationmixed integer programrounding algorithm

Mathematics Subject Classification ID

Mixed integer programming (90C11) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• k-violation linear programming
• scientific article; zbMATH DE number 686977
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
• Covering linear programming with violations
• scientific article; zbMATH DE number 4215407
• Approximating covering integer programs with multiplicity constraints
• Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
• A new approximation algorithm for k-set cover problem
• Primal-dual approximation algorithms for submodular vertex cover problems with linear/submodular penalties

Cites work

• k-violation linear programming
• Algorithms for facility location problems with outliers. (Extended abstract)
• An approximation algorithm for the partial covering 0-1 integer program
• Approximation algorithms for partial covering problems
• Covering linear programming with violations
• scientific article; zbMATH DE number 5764796 (Why is no real title available?)
• Local ratio method on partial set multi-cover
• Low-Dimensional Linear Programming with Violations
• Packing interdiction and partial covering problems
• Relaxations and approximations of chance constraints under finite distributions

Cited in

(2)

• k-violation linear programming
• Covering linear programming with violations

This page was built for publication: Approximation algorithms for the covering-type \(k\)-violation linear program

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