Approximation algorithms for covering/packing integer programs

详细信息    查看全文

• 作者：Stavros G. Kolliopoulos and Neal E. Young
• 关键词：Covering/packing integer programs ; Set cover ; Approximation algorithms ; Multiplicity constraints
• 刊名：Journal of Computer and System Sciences
• 出版年：2005
• 出版时间：2005
• 年：2005
• 卷：71
• 期：4
• 页码：495-505
• 全文大小：201 K

文摘

Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing g src=""http://www.sciencedirect.com/cache/MiamiImageURL/B6WJ0-4GX1J6S-1-7/0?wchp=dGLbVzb-zSkWb"" alt=""Click to view the MathML source"" align=""absbottom"" border=""0"" height=21 width=305>. We give a bicriteria-approximation algorithm that, given εg src=""http://www.sciencedirect.com/scidirimg/entities/2208.gif"" alt=""set membership, variant"" border=0>(0,1], finds a solution of cost O(ln(m)/ε²) times optimal, meeting the covering constraints (Axg src=""http://www.sciencedirect.com/scidirimg/entities/2a7e.gif"" alt=""greater-or-equal, slanted"" border=0>a) and multiplicity constraints (xg src=""http://www.sciencedirect.com/scidirimg/entities/2a7d.gif"" alt=""less-than-or-equals, slant"" border=0>d), and satisfying Bxg src=""http://www.sciencedirect.com/scidirimg/entities/2a7d.gif"" alt=""less-than-or-equals, slant"" border=0>(1+ε)b+β, where β is the vector of row sums β_i