Oct. Nov. 2017 Dec.
SunMonTueWedThuFriSat
29303101020304
05060708091011
12131415161718
19 202122232425
26 272829300102
Click Seminar

Past Seminars

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