A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions

DOI10.1007/978-3-030-92681-6_9OpenAlexW4205934954MaRDI QIDQ2149859

Ling Gai, Min Cui, Ruiqi Yang, Dong-lei Du

Publication date: 29 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92681-6_9

zbMATH Keywords

cardinality-constrainedstreaminglinear-timenon-submodular

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Submodular maximization meets streaming: matchings, matroids, and more
• Parametric monotone function maximization with matroid constraints
• Non-submodular streaming maximization with minimum memory and low adaptive complexity
• Non-submodular maximization on massive data streams
• Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
• Online Submodular Maximization with Preemption
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Fast algorithms for maximizing monotone nonsubmodular functions
• Maximize a monotone function with a generic submodularity ratio

This page was built for publication: A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions