An improved analysis of the Greedy+Singleton algorithm for k-submodular knapsack maximization

DOI10.1007/978-3-031-39344-0_2MaRDI QIDQ6535797zbMATH OpenFDO

Authors Zhongzheng Tang, Jingwen Chen, Chenhao Wang

Publication date 28 February 2024

Full work available at URL https://doi.org/10.1007/978-3-031-39344-0_2

zbMATH Keywords

\(k\)-submodularityapproximationgreedyknapsack

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
• Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
• On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A refined analysis of submodular greedy
• An exact cutting plane method for k-submodular function maximization
• Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
• Improved approximation algorithms for \(k\)-submodular function maximization
• Improved randomized algorithm for k-submodular function maximization
• Maximization of k-submodular function with a matroid constraint
• Maximizing k-submodular functions and beyond
• Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms
• Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
• Monotone k-submodular secretary problems: cardinality and knapsack constraints
• On \(k\)-submodular relaxation
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints
• Practical budgeted submodular maximization
• The budgeted maximum coverage problem
• Towards minimizing k-submodular functions

Cited in

(4)

• Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
• Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
• Profit maximization for competitive influence spread in social networks
• Deterministic algorithms for k-submodular maximization with the chance constraint

This page was built for publication: An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization

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