Submodular Maximization Subject to a Knapsack Constraint Under Noise Models

DOI10.1142/S0217595922500130MaRDI QIDQ5888385zbMATH OpenOpenAlexFDO

Authors Canh V. Pham, Huan X. Hoang

Publication date 25 April 2023

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

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

zbMATH Keywords

approximation algorithmknapsack constraintsubmodularnoises

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Recommendations

• Streaming submodular maximization under \(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
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Algorithms for maximizing monotone submodular function minus modular function under noise

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• A note on maximizing a submodular set function subject to a knapsack constraint
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An analysis of approximations for maximizing submodular set functions—I
• Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
• Fast algorithms for maximizing submodular functions
• Learning with submodular functions: a convex optimization perspective
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing social influence in nearly optimal time
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Optimal approximation for the submodular welfare problem in the value oracle model
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• The budgeted maximum coverage problem

Cited in

(4)

• Per-round knapsack-constrained linear submodular bandits
• Algorithms for maximizing monotone submodular function minus modular function under noise
• Bicriteria algorithms for maximizing the difference between submodular function and linear function under noise
• Submodular maximization over data streams with differential privacy noise

This page was built for publication: Submodular Maximization Subject to a Knapsack Constraint Under Noise Models

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