An optimal streaming algorithm for non-submodular functions maximization on the integer lattice

Bin Liu (), Zihan Chen, Huijuan Wang () and Weili Wu ()
Additional contact information
Bin Liu: Ocean University of China
Zihan Chen: Ocean University of China
Huijuan Wang: Qingdao University
Weili Wu: The University of Texas at Dallas

Journal of Combinatorial Optimization, 2023, vol. 45, issue 1, No 46, 17 pages

Abstract: Abstract Submodular optimization problem has been concerned in recent years. The problem of maximizing submodular and non-submodular functions on the integer lattice has received a lot of recent attention. In this paper, we study streaming algorithms for the problem of maximizing a monotone non-submodular functions with cardinality constraint on the integer lattice. For a monotone non-submodular function $$f:{\textbf {Z}}^{n}_{+}\rightarrow {\textbf {R}}_{+}$$ f : Z + n → R + defined on the integer lattice with diminishing-return (DR) ratio $$\gamma $$ γ , we present a one pass streaming algorithm that gives a $$(1-\frac{1}{2^{\gamma }}-\epsilon )$$ ( 1 - 1 2 γ - ϵ ) -approximation, requires at most $$O(k\epsilon ^{-1}\log {k/\gamma })$$ O ( k ϵ - 1 log k / γ ) space and $$O(\epsilon ^{-1}\log {k/\gamma }\cdot $$ O ( ϵ - 1 log k / γ · $$\log {\Vert {\textbf {B}}\Vert _{\infty }})$$ log ‖ B ‖ ∞ ) update time per element. We then modify the algorithm and improve the memory complexity to $$O(\frac{k}{\gamma \epsilon })$$ O ( k γ ϵ ) . To the best of our knowledge, this is the first streaming algorithm on the integer lattice for this constrained maximization problem.

Keywords: Streaming algorithm; Cardinality constraint; Non-submodular maximization; Integer lattice (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-00975-7 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-00975-7

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

DOI: 10.1007/s10878-022-00975-7

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 ().