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

DOI10.1016/J.TCS.2022.09.028MaRDI QIDQ2089671zbMATH OpenOpenAlexFDO

Authors Jingjing Tan, Fengmin Wang, Weina Ye, Yang Zhou, 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 latticeknapsack constraintstreaming algorithmsnon-submodular

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 5485514 (Why is no real title available?)
• A note on maximizing a submodular set function subject to a knapsack constraint
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• An analysis of approximations for maximizing submodular set functions—I
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
• Maximizing a monotone submodular function subject to a matroid constraint
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Non-submodular maximization on massive data streams
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• Online submodular maximization with preemption
• 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
• Randomized MWU for positive LPs
• Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• Submodular function maximization in parallel via the multilinear relaxation

Cited in

(5)

• Streaming algorithms for maximizing DR-submodular functions with d-knapsack constraints
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice

This page was built for publication: Streaming algorithms for monotone non-submodular function maximization under a 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 Q2089671)