Approximate fixed-rank closures of covering problems

• 成果类型: Article
• 署名作者: Bienstock, D; Zuckerberg, M
• 署名单位: Columbia University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0598-z
• 发表日期: 2006
• 页码: 9-27
• 关键词: relaxations; cuts

摘要

Consider a 0/1 integer program min{c(T) x : Ax >= b, x epsilon {0, 1}(n)} where A is nonnegative. We show that if the number of minimal covers of Ax >= b is polynomially bounded, then for any epsilon > 0 and any fixed q, there is a polynomially large lift-and-project relaxation whose value is at least (1 - epsilon) times the value of the rank <= q relaxation. A special case of this result is that given by set-covering problems, or, generally, problems where the coefficients in A and b are bounded.