Speaker: Tasuku Soma, Graduate School of Information Science and
Technology, the University of Tokyo
https://www.opt.mist.i.u-tokyo.ac.jp/~tasuku/

Abstract:

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.