Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice
From MaRDI portal
Publication:5024476
DOI10.1142/S0217595921400042zbMath1481.90218MaRDI QIDQ5024476
Yishui Wang, Longkun Guo, Dongmei Zhang, Zhenning Zhang, Da-Chuan Xu
Publication date: 1 February 2022
Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)
cardinality; integer lattice; submodular maximization; streaming algorithm; diminishing return submodular
90B80: Discrete location and assignment
Related Items
A binary search double greedy algorithm for non-monotone DR-submodular maximization, An optimal streaming algorithm for non-submodular functions maximization on the integer lattice, Profit maximization in social networks and non-monotone DR-submodular maximization
Cites Work
- Unnamed Item
- Unnamed Item
- A note on maximizing a submodular set function subject to a knapsack constraint
- Maximizing monotone submodular functions over the integer lattice
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- An analysis of approximations for maximizing submodular set functions—I
- Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
- Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
- Online Submodular Maximization with Preemption
- Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
- Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
