No-regret Algorithms for Online K-submodular Maximization

Tasuku Soma Algorithms Seminars
September 5, 2019 3:30 pm ICICS X836

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.