Streaming algorithms for non-submodular functions maximization with d-knapsack constraint on the Integer lattice

DOI10.1142/S0217595923400183MaRDI QIDQ6542993zbMATH OpenFDO

Authors Jingjing Tan, Ruiqi Yang, Yapu Zhang, Mingyue Zhu

Publication date 23 May 2024

Published in Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0217595923400183

zbMATH Keywords

integer latticeknapsack constraintnon-submodular functionstreaming algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
• Streaming algorithms for maximizing DR-submodular functions with d-knapsack constraints
• An optimal streaming algorithm for non-submodular functions maximization on the integer lattice
• Streaming submodular maximization under \(d\)-knapsack constraints
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

Cites work

• A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
• Non-submodular maximization on massive data streams
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• Online submodular welfare maximization: greedy is optimal
• Optimal approximation for the submodular welfare problem in the value oracle model
• Parametric monotone function maximization with matroid constraints
• Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
• Submodular function maximization in parallel via the multilinear relaxation
• Submodular function maximization on the bounded integer lattice
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time

Cited in

(1)

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

This page was built for publication: Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6542993)