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

0-1 covering problemgreedy algorithmset coverings

Mathematics Subject Classification ID

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

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)

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

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)