An Extension of the Lovász Local Lemma, and its Applications to Integer Programming

DOI10.1137/S0097539703434620zbMath1117.60012OpenAlexW2125674105WikidataQ124810119 ScholiaQ124810119MaRDI QIDQ3446810

Aravind Srinivasan

Publication date: 26 June 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539703434620

zbMATH Keywords

discrepancyapproximation algorithmsrandomized roundingLovász local lemmacolumn-sparse integer programs

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Combinatorial probability (60C05)

Related Items (7)

Partial Resampling to Approximate Covering Integer Programs ⋮ A variable neighborhood search algorithm for the multimode set covering problem ⋮ Approximability of sparse integer programs ⋮ Multimode extensions of combinatorial optimization problems ⋮ An estimate for the probability of dependent events ⋮ Approximating Sparse Covering Integer Programs Online ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem

This page was built for publication: An Extension of the Lovász Local Lemma, and its Applications to Integer Programming