On the Greedy Heuristic for Continuous Covering and Packing Problems
From MaRDI portal
Publication:4750653
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
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