Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint
- 3 January 2021
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 83 (3) , 879-902
Abstract
No abstract availableKeywords
Funding Information
- Japan Society for the Promotion of Science (JP17K00028, JP18H05291)
- Agence Nationale de la Recherche (ANR-19-CE48-0016)
- Agence Nationale de la Recherche (ANR-18-CE40-0025-01)
This publication has 21 references indexed in Scilit:
- Submodular maximization meets streaming: matchings, matroids, and moreMathematical Programming, 2015
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution SchemesSIAM Journal on Computing, 2014
- Monotone Submodular Maximization over a Matroid via Non-Oblivious Local SearchSIAM Journal on Computing, 2014
- Fast algorithms for maximizing submodular functions2013
- Maximizing a Monotone Submodular Function Subject to a Matroid ConstraintSIAM Journal on Computing, 2011
- Submodular Maximization over Multiple Matroids via Generalized Exchange PropertiesMathematics of Operations Research, 2010
- A note on maximizing a submodular set function subject to a knapsack constraintOperations Research Letters, 2004
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location ProblemsMathematics of Operations Research, 1982
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- An analysis of approximations for maximizing submodular set functions—II1978