Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint

DOI10.1016/j.cor.2023.106452MaRDI QIDQ6065659

Unnamed Author, Canh V. Pham, Tan D. Tran

Publication date: 15 November 2023

Published in: Computers \& Operations Research (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationapproximation algorithmknapsack constraint\(k\)-submodular

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multi-level facility location as the maximization of a submodular set function
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• Derandomization for \(k\)-submodular maximization
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• Large-scale influence maximization via maximal covering location
• Submodularity and local search approaches for maximum capture problems under generalized extreme value models
• Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms
• A mobile multi-agent sensing problem with submodular functions under a partition matroid
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• Improved Approximation Algorithms for k-Submodular Function Maximization
• Maximizing Social Influence in Nearly Optimal Time
• Using submodularity in solving the robust bandwidth packing problem with queuing delay guarantees
• Efficient sensor placement and online scheduling of bin collection

This page was built for publication: Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint