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

DOI10.1016/J.TCS.2022.09.028OpenAlexW4297372942MaRDI QIDQ2089671FDOQ2089671

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

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

zbMATH Keywords

integer latticeknapsack constraintstreaming algorithmsnon-submodular

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Maximizing a monotone submodular function subject to a matroid constraint
• An analysis of approximations for maximizing submodular set functions—I
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Title not available (Why is that?)
• A note on maximizing a submodular set function subject to a knapsack constraint
• Optimal approximation for the submodular welfare problem in the value oracle model
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• 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
• Online submodular welfare maximization: greedy is optimal
• Online submodular maximization with preemption
• Parametric monotone function maximization with matroid constraints
• Non-submodular maximization on massive data streams
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• 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
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• Submodular function maximization in parallel via the multilinear relaxation
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Randomized MWU for positive LPs

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)