Random approximation algorithms for monotone k-submodular function maximization with size constraints

DOI10.1007/978-3-031-39344-0_9MaRDI QIDQ6535807FDOQ6535807

Min Li, Yang Zhou, Yuying Li, Qian Liu

Publication date: 28 February 2024

zbMATH Keywords

approximation algorithmssize constraints\(k\)-submodular function

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• A note on maximizing a submodular set function subject to a knapsack constraint
• Maximizing k -Submodular Functions and Beyond
• Maximization of \(k\)-submodular function with a matroid constraint
• Towards Minimizing k-Submodular Functions
• On \(k\)-submodular relaxation
• Improved Approximation Algorithms for k-Submodular Function Maximization
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
• Improved Randomized Algorithm for k-Submodular Function Maximization
• Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms

This page was built for publication: Random approximation algorithms for monotone \(k\)-submodular function maximization with size constraints

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