Stochastic packing integer programs with few queries

• 成果类型: Article
• 署名作者: Maehara, Takanori; Yamaguchi, Yutaro
• 署名单位: University of Osaka; RIKEN
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01388-x
• 发表日期: 2020
• 页码: 141-174
• 关键词: algorithm

摘要

We consider a stochastic variant of the packing-type 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 a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those 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.