A Streaming Model for Monotone Lattice Submodular Maximization with a Cardinality Constraint

摘要

In this paper, we consider a streaming model of maximizing monotone lattice submodular function with a cardinality constraint on the integer lattice. As (lattice) submodularity does not imply the diminishing return property on the integer lattice, we introduce the Sieve-Streaming algorithm combining with a modified binary search subroutine to solve the problem. We also show it is with an approximation ratio 1/2 -∈, a memory complexity O(∈~(-1)k log k), and a query complexity O(∈~(-2) log~2 k) per element.