User menu

An Analysis of the Greedy Algorithm for the Submodular Set Covering Problem

Bibliographic reference Wolsey, Laurence. An Analysis of the Greedy Algorithm for the Submodular Set Covering Problem. In: Combinatorica, Vol. 2, no. 4, p. 385-393 (1982)
Permanent URL http://hdl.handle.net/2078.1/56685
  1. V. Chvatal, Greedy Heuristics for the Set-Covering Problem,Math. of Oper. Res. 4 (3), (1979), 233–235.
  2. G. Cornuéjols, G. L. Nemhauser andL. A. Wolsey, A Canonical Representation of Simple Plant Location Problems and Its Applications,SIAM J. Alg. Disc. Math. 1, (1980), 261–272.
  3. G. Dobson, Worst Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data,Technical Report SOL 80-25, Stanford, October 1980.
  4. M. L. Fisher andL. A. Wolsey, On the Greedy Heuristic for Covering and Packing Problems,CORE, DP 8124, Louvain-la-Neuve, May 1981.
  5. D. S. Johnson, Approximation Algorithms for Combinatorial problems,J. Comput. System Sci. 9, (1974), 256–298.
  6. L. Lovász. On the Ratio of Optimal Integral and Fractional Covers,Discrete Math.,13, (1975), 383–390.
  7. G. L. Nemhauser, L. A. Wolsey andM. L. Fisher, An Analysis of Approximations for Maximizing Submodular Set Functions — I.Math. Prog.,14 (1978), 265–294.
  8. G. L. Nemhauser andL. A. Wolsey, Maximising Submodular Set Functions: Formulations and Analysis of Algorithms,CORE, DP 7832, Louvain La-Neuve, August 1978, to appear in Ann. of. Disc. Math.
  9. R. Rado, Note on Independence Functions,Proc. London Math. Soc.,7, (1957), 300–320.
  10. L. A. Wolsey, Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems,Math. of Oper. Res. 7, (1982), 410–425,