Maximization of k-submodular function with a matroid constraint

DOI10.1007/978-3-031-20350-3_1MaRDI QIDQ6111937zbMATH OpenFDO

Authors

Publication date 4 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-20350-3_1

zbMATH Keywords

\(k\)-submodular functiondeterministic algorithmmatroid constraintrandomized algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Bisubmodular Function Minimization
• Improved approximation algorithms for \(k\)-submodular function maximization
• Improved randomized algorithm for k-submodular function maximization
• Maximizing k-submodular functions and beyond
• Monotone k-submodular secretary problems: cardinality and knapsack constraints
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• Ottimizzazione Combinatoria
• Towards minimizing k-submodular functions

Cited in

(16)

• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• Approximation guarantees for deterministic maximization of submodular function with a matroid constraint
• Robust Maximization of Correlated Submodular Functions Under Cardinality and Matroid Constraints
• Maximizing a class of submodular utility functions with constraints
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization
• Random approximation algorithms for monotone \(k\)-submodular function maximization with size constraints
• Efficient algorithms for k-submodular function maximization with p-system and d-knapsack constraint
• \textsc{Greedy+Max}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• k-submodular and approximately non-k-submodular maximization under p-system and knapsack constraints
• Approximately non-k-submodular maximization under p-system and knapsack constraints
• Maximizing a k-submodular function with p-system constraints
• Streaming algorithms for maximizing k-submodular functions under a partition matroid constraint
• Approximation algorithms for k-submodular maximization under fairness constraints and size constraints
• Deterministic algorithms for k-submodular maximization with the chance constraint

This page was built for publication: Maximization of \(k\)-submodular function with a matroid constraint

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