Hiroki Oshima

dblp:188/6376 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
1since 2021 · last 2021
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 1 since 2021
YearPublicationVenuePosition
2021 Improved Randomized Algorithm for k-Submodular Function Maximization
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 an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained $k$-submodular maximization, Iwata, Tanigawa, and Yoshida, [ Improved approximation algorithms for $k$-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] gave a randomized $k/(2k-1)$-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a $\frac{k^2+1}{2k^2+1}$-approximation for $k\geq 3$. We also give a randomized $\frac{\sqrt{17}-3}{2}$-approximation algorithm for $k=3$. We use the same framework used in Iwata, Tanigawa, and Yoshida, [ Improved approximation algorithms for $k$-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and Živný [ ACM Trans. Algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities.
Hiroki Oshima
SIAM J. Discret. Math.1
2017 Derandomization for k-Submodular Maximization
Hiroki Oshima
IWOCA1