Randomized Strategies for Robust Combinatorial Optimization

Presenter | 講演者

Hanna Sumita | 澄田範奈

Tokyo Institute of Technology | 東京工業大学

Biography | 略歴

I am an associate professor (lecturer) at Tokyo Institute of Technology from April 2020. Before this, I was an assistant professor at Tokyo Metropolitan University, and a project researcher of JST, ERATO Kawarabayashi Large Graph Project at National Institute of Informatics. I obtained my Ph.D. from University of Tokyo in 2015.

2015年3月,東京大学大学院情報理工学系研究科 博士(情報理工学)取得.国立情報学研究所特任研究員,首都大学東京(現 東京都立大学)助教を経て,2020年4月より,東京工業大学情報理工学院 講師.

Abstract | 概要

We aim to solve combinatorial optimization problems under uncertainty on objective functions. The problem is to maximize the minimum function value between given candidates of an objective function. This problem can be regarded as the problem of computing an equilibrium in a two-person zero-sum game. Existing research mainly focuses on a deterministic solution, and few papers work on a randomized one. In this talk, we propose two frameworks for computing an optimal randomized solution based on linear programming and the multiplicative weight update method. We also demonstrate that these frameworks yield approximation algorithms for important classes. This is joint work with Yasushi Kawase.