VLDB 2026 Research / reviewers in the wild / expert
Hiroki Oshima
dblp:188/6376
· DBLP profile ↗
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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2021 | Improved Randomized Algorithm for k-Submodular Function MaximizationabstractSubmodularity 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 |
IWOCA | 1 |