Streaming submodular maximization under d-knapsack constraints

Zihan Chen, Bin Liu () and Hongmin W. Du
Additional contact information
Zihan Chen: Ocean University of China
Bin Liu: Ocean University of China
Hongmin W. Du: Rutgers University

Journal of Combinatorial Optimization, 2023, vol. 45, issue 1, No 25, 21 pages

Abstract: Abstract Submodular optimization is a key topic in combinatorial optimization, which has attracted extensive attention in the past few years. Among the known results, most of the submodular functions are defined on set. But recently some progress has been made on the integer lattice. In this paper, we study two problem of maximizing submodular functions with d-knapsack constraints. First, for the problem of maximizing DR-submodular functions with d-knapsack constraints on the integer lattice, we propose a one pass streaming algorithm that achieves a $$\frac{1-\theta }{1+d}$$ 1 - θ 1 + d -approximation with $$O\left( \frac{\log (d\beta ^{-1})}{\beta \epsilon }\right) $$ O log ( d β - 1 ) β ϵ memory complexity and $$O\left( \frac{\log (d\beta ^{-1})}{\epsilon }\log \Vert {\textbf {b}} \Vert _{\infty }\right) $$ O log ( d β - 1 ) ϵ log ‖ b ‖ ∞ update time per element, where $$\theta =\min (\alpha +\epsilon , 0.5+\epsilon )$$ θ = min ( α + ϵ , 0.5 + ϵ ) and $$\alpha , \beta $$ α , β are the upper and lower bounds for the cost of each item in the stream. Then we devise an improved streaming algorithm to reduce the memory complexity to $$O(\frac{d}{\beta \epsilon })$$ O ( d β ϵ ) with unchanged approximation ratio and query complexity. Then for the problem of maximizing submodular functions with d-knapsack constraints under noise, we design a one pass streaming algorithm. When $$\varepsilon \rightarrow 0$$ ε → 0 , it achieves a $$\frac{1}{1-\alpha +d}$$ 1 1 - α + d -approximate ratio, memory complexity $$O\left( \frac{\log (d\beta ^{-1})}{\beta \epsilon }\right) $$ O log ( d β - 1 ) β ϵ and query complexity $$O\left( \frac{\log (d\beta ^{-1})}{\epsilon }\right) $$ O log ( d β - 1 ) ϵ per element. As far as we know, these two are the first streaming algorithms under their corresponding problems.

Keywords: Streaming algorithm; d-Knapsack constraints; Integer lattice; Noise (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00951-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:1:d:10.1007_s10878-022-00951-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00951-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().