Jui. Aug. 2017 Sep.
SunMonTueWedThuFriSat
303101 02030405
06070809101112
13141516171819
20 212223242526
27 282930310102
Click Seminar

Next Seminar

DateAugust 21, 2017 (Monday)
Time15:00-16:00
SpeakerYutaro Yamaguchi 
ProfileAssistant Prof. at Osaka University
TitleStochastic Packing Integer Programs with Few Queries 
Abstract
We consider a stochastic variant of the integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose adaptive and non-adaptive algorithms for this problem, and provide a general technique for analyzing the performance of the algorithms. We also demonstrate our framework by applying it to a variety of stochastic combinatorial optimization problems such as matching, matroid, and stable set problems. This is a joint work with Takanori Maehara in RIKEN AIP.
Site
Time16:00-17:00
SpeakerYuya Yoshikawa 
Profile
Title 
Abstract
Site