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

DOI10.1007/978-3-031-49611-0_21MaRDI QIDQ6606191zbMATH OpenFDO

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

Publication date 16 September 2024

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

zbMATH Keywords

\(k\)-submodularityapproximationknapsack constraint

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites work

• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 7051294 (Why is no real title available?)
• 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
• Submodular maximization with cardinality constraints
• Towards minimizing k-submodular functions

This page was built for publication: \textsc{Greedy+Max}: an efficient approximation 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 Q6606191)