Speaker: Tasuku Soma, Graduate School of Information Science and
Technology, the University of Tokyo
We present a polynomial time algorithm for online maximization of k-submodular functions. For online (nonmonotone) k-submodular maximization, our algorithm achieves a tight approximate factor in the approximate regret. For online monotone k-submodular maximization, our approximate-regret matches to the best-known approximation ratio, which is tight asymptotically as k tends to infinity. Our approach is based on the Blackwell approachability theorem and online linear optimization.