New class of 0-1 integer programs with tight approximation via linear relaxations

DOI10.1007/S001860100115MaRDI QIDQ1396978zbMATH OpenOpenAlexFDO

Authors Armen S. Asratian, N. N. Kuzyurin

Publication date 15 July 2003

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001860100115

zbMATH Keywords

integer programmingapproximationrandomized rounding

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Boolean programming (90C09)

Recommendations

• Approximation of optima of integer programs of the packing—covering type
• Approximating integer programs with positive right-hand sides
• Optima of dual integer linear programs
• Approximability of Sparse Integer Programs
• Randomized metarounding

Cited in

(6)

• Nearness and bound relationships between an integer-programming problem and its relaxed linear-programming problem
• Approximation of optima of integer programs of the packing—covering type
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Separation between estimation and approximation
• Approximating integer programs with positive right-hand sides
• scientific article; zbMATH DE number 913269 (Why is no real title available?)

This page was built for publication: New class of 0-1 integer programs with tight approximation via linear relaxations

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