| 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. |
