A Sharp Bound on the Ratio Between Optimal Integer and Fractional Covers

DOI10.1287/MOOR.9.1.1MaRDI QIDQ3323708zbMATH OpenOpenAlexFDO

Authors E. Balas

Publication date 1984

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.9.1.1

zbMATH Keywords

best possible boundheuristicoptimal fractional solutionset covering

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Integer programming (90C10)

Recommendations

• Fractional v. integral covers in hypergraphs of bounded edge size
• On the Fractional Covering Number of Hypergraphs
• Bounds for optimal coverings
• Bounds for optimal coverings
• scientific article; zbMATH DE number 7559412
• Fractional covers of hypergraphs with bounded multi-intersection
• Fractional covers and matchings in families of weighted \(d\)-intervals
• Sharp lower bounds on the fractional matching number
• On fractional cut covers
• Optimal fractional matchings and covers in infinite hypergraphs: existence and duality

Cited in

(7)

• Pareto optimality and a class of set covering heuristics
• Rounding algorithms for covering problems
• A-priori upper bounds for the set covering problem
• Minimum ratio cover of matrix columns by extreme rays of its induced cone
• Absolute bounds on optimal cost for a class of set covering problems
• Hitting times of local and global optima in genetic algorithms with very high selection pressure
• A sharp result on m-covers

This page was built for publication: A Sharp Bound on the Ratio Between Optimal Integer and Fractional Covers

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