Non-submodular streaming maximization with minimum memory and low adaptive complexity

DOI10.1007/978-3-030-57602-8_20zbMath1485.90112OpenAlexW3048291236MaRDI QIDQ2039664

Meixia Li, Xueling Zhou, Wenchao Wang, Jingjing Tan

Publication date: 5 July 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-57602-8_20

zbMATH Keywords

cardinality constraintstreaming algorithmnon-submodular functions

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (2)

A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions ⋮ Fast algorithms for maximizing monotone nonsubmodular functions

Cites Work

• Unnamed Item
• Unnamed Item
• Simultaneous approximation of multi-criteria submodular function maximization
• Submodular maximization meets streaming: matchings, matroids, and more
• A note on maximizing a submodular set function subject to a knapsack constraint
• Non-submodular maximization on massive data streams
• A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem
• A threshold of ln n for approximating set cover
• Streaming Algorithms for Submodular Function Maximization
• Data Streams: Algorithms and Applications
• Approximate counting of inversions in a data stream
• An analysis of approximations for maximizing submodular set functions—I
• Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Online Submodular Maximization with Preemption
• Fast algorithms for maximizing submodular functions
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search

This page was built for publication: Non-submodular streaming maximization with minimum memory and low adaptive complexity