Randomized approximation algorithms for monotone k-submodular function maximization with constraints

DOI10.1007/S10878-025-01299-YMaRDI QIDQ6976863zbMATH OpenFDO

Authors Yuying Li, M. Li, Yang Zhou, Shuxian Niu, Qian Liu

Publication date 31 May 2025

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-025-01299-Y

zbMATH Keywords

\(k\)-submodular functionapproximation algorithmsindividual size constraintsmatroid constraintsrandomized algorithms

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Derandomization for k-submodular maximization
• Improved approximation algorithms for \(k\)-submodular function maximization
• Maximizing k-submodular functions and beyond
• Maximizing a monotone submodular function subject to a matroid constraint
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• Random approximation algorithms for monotone \(k\)-submodular function maximization with size constraints
• Towards minimizing k-submodular functions

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

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