Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice

DOI10.1016/j.tcs.2022.09.028OpenAlexW4297372942MaRDI QIDQ2089671

Weina Ye, Fengmin Wang, Yang Zhou, Jingjing Tan, Xiao-Qing Zhang

Publication date: 24 October 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.09.028

zbMATH Keywords

integer latticestreaming algorithmsknapsack constraintnon-submodular

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular maximization meets streaming: matchings, matroids, and more
• A note on maximizing a submodular set function subject to a knapsack constraint
• Maximizing monotone submodular functions over the integer lattice
• Parametric monotone function maximization with matroid constraints
• Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
• Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
• Non-submodular maximization on massive data streams
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• An analysis of approximations for maximizing submodular set functions—I
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Submodular Function Maximization in Parallel via the Multilinear Relaxation
• Online Submodular Maximization with Preemption
• Online submodular welfare maximization: Greedy is optimal
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

This page was built for publication: Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice