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

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

Authors: Yuying Li, Min Li, Yang Zhou, 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)