Approximation algorithms for the covering-type \(k\)-violation linear program

DOI10.1007/s11590-019-01425-wzbMath1431.90097OpenAlexW2937542057MaRDI QIDQ2329669

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

approximation algorithmslinear relaxationrounding algorithmmixed integer program\(k\)-violation linear program

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• \(k\)-violation linear programming
• Relaxations and approximations of chance constraints under finite distributions
• An approximation algorithm for the partial covering 0-1 integer program
• Local ratio method on partial set multi-cover
• Covering Linear Programming with Violations
• Approximation algorithms for partial covering problems
• Packing Interdiction and Partial Covering Problems
• Low-Dimensional Linear Programming with Violations

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