Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem
Authors:
- Michele ConfortiMCMichele Conforti
- Gérard CornuéjolsGCGérard Cornuéjols
- 1 March 1984
- journal article
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 7 (3) , 251-274
Abstract
No abstract availableThis publication has 7 references indexed in Scilit:
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- An Analysis of the Greedy Heuristic for Independence Systems1978
- An analysis of approximations for maximizing submodular set functions—II1978
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate AlgorithmsManagement Science, 1977
- Matroids and the greedy algorithmMathematical Programming, 1971
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956