\textsc{Greedy+Max}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization

DOI10.1007/978-3-031-49611-0_21MaRDI QIDQ6606191

Weijia Jia, Zhongzheng Tang, Chenhao Wang, Jingwen Chen, Tian Wang

Publication date: 16 September 2024

zbMATH Keywords

approximationknapsack constraint\(k\)-submodularity

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints
• Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• On $k$-Submodular Relaxation
• A threshold of ln n for approximating set cover
• Towards Minimizing k-Submodular Functions
• An analysis of approximations for maximizing submodular set functions—I
• Improved Approximation Algorithms for k-Submodular Function Maximization
• Maximizing k -Submodular Functions and Beyond
• Submodular Maximization with Cardinality Constraints
• Improved Randomized Algorithm for k-Submodular Function Maximization
• Maximization of \(k\)-submodular function with a matroid constraint
• 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

This page was built for publication: \textsc{Greedy+Max}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization