On the Greedy Heuristic for Continuous Covering and Packing Problems

DOI10.1137/0603059zbMath0512.05017OpenAlexW2001911901MaRDI QIDQ4750653

Marshall L. Fisher, Laurence A. Wolsey

Publication date: 1982

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

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

zbMATH Keywords

greedy algorithmset coverings0-1 covering problem

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorial aspects of packing and covering (05B40)

Related Items (12)

Partial Resampling to Approximate Covering Integer Programs ⋮ Rounding algorithms for covering problems ⋮ Local ratio method on partial set multi-cover ⋮ Approximating covering integer programs with multiplicity constraints ⋮ Approximating integer programs with positive right-hand sides ⋮ Approximation algorithm for partial positive influence problem in social network ⋮ Model-based view planning ⋮ An ex-post bound on the greedy heuristic for the uncapacitated facility location problem ⋮ An analysis of the greedy algorithm for the submodular set covering problem ⋮ Approximation algorithms for covering/packing integer programs ⋮ Order selection on a single machine with high set-up costs ⋮ The maximum clique problem

Cites Work

• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Heuristic analysis, linear programming and branch and bound
• A Greedy Heuristic for the Set-Covering Problem
• Worst-Case Analysis of Heuristic Algorithms
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• An analysis of approximations for maximizing submodular set functions—I

This page was built for publication: On the Greedy Heuristic for Continuous Covering and Packing Problems