On the Greedy Heuristic for Continuous Covering and Packing Problems

DOI10.1137/0603059MaRDI QIDQ4750653zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

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

Cited in

(11)

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

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

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