Improved Randomized Algorithm for k-Submodular Function Maximization
Author:
- Hiroki OshimaHOHiroki Oshima
- 5 January 2021
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 35 (1) , 1-22
Abstract
Submodularity is one of the most important properties in combinatorial optimization, and $k$-submodularity is a generalization of submodularity. Maximization of a $k$-submodular function requires a...Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Maximizing k -Submodular Functions and BeyondACM Transactions on Algorithms, 2016
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular MaximizationSIAM Journal on Computing, 2015
- Maximizing Non-monotone Submodular FunctionsSIAM Journal on Computing, 2011
- A combinatorial strongly polynomial algorithm for minimizing submodular functionsJournal of the ACM, 2001
- A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial TimeJournal of Combinatorial Theory, Series B, 2000
- Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functionsMathematical Programming, 1984
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981