On the Greedy Heuristic for Continuous Covering and Packing Problems

DOI10.1137/0603059zbMATH Open0512.05017OpenAlexW2001911901MaRDI QIDQ4750653FDOQ4750653

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

• Approximation algorithms for combinatorial problems
• A Greedy Heuristic for the Set-Covering Problem
• On the ratio of optimal integral and fractional covers
• An analysis of approximations for maximizing submodular set functions—I
• 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
• 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)