Improved Randomized Algorithm for k-Submodular Function Maximization
From MaRDI portal
Publication:5855531
DOI10.1137/19M1277692zbMath1461.90123arXiv1907.12942MaRDI QIDQ5855531
Publication date: 18 March 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.12942
Related Items (9)
Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints ⋮ On maximizing a monotone \(k\)-submodular function under a knapsack constraint ⋮ Maximization of \(k\)-submodular function with a matroid constraint ⋮ Weakly \(k\)-submodular maximization under matroid constraint ⋮ Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm ⋮ Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint ⋮ \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ k-Submodular maximization with two kinds of constraints
Cites Work
- The ellipsoid method and its consequences in combinatorial optimization
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Maximizing Non-monotone Submodular Functions
- Towards Minimizing k-Submodular Functions
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
- Deterministic Algorithms for Submodular Maximization Problems
- Improved Approximation Algorithms for k-Submodular Function Maximization
- An Algorithm for Submodular Functions on Graphs
- Maximizing k -Submodular Functions and Beyond
This page was built for publication: Improved Randomized Algorithm for k-Submodular Function Maximization
