Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice

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)

zbMATH Keywords

cardinalityinteger latticesubmodular maximizationstreaming algorithmdiminishing return submodular

Mathematics Subject Classification ID

Discrete location and assignment (90B80)

Related Items (3)

An optimal streaming algorithm for non-submodular functions maximization on the integer lattice ⋮ A binary search double greedy algorithm for non-monotone DR-submodular maximization ⋮ 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

This page was built for publication: Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice