Stochastic Packing Integer Programs with Few Queries
Stochastic Packing Integer Programs with Few Queries
复制标题
具有少量查询的随机打包整数程序
DOI：
10.1137/1.9781611975031.21
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Maehara Takanori
中科院分区：
文献类型：
--
作者：
Yamaguchi Yutaro;Maehara Takanori
我们考虑一个随机变量的包装型整数线性规划问题，其中包含随机变量的目标向量。我们被允许通过进行查询来揭示目标向量的每个条目，任务是通过进行少量的查询来找到一个好的解决方案。我们提出了一个通用的框架，自适应和非自适应算法，这个问题，并提供了一个统一的方法来分析这些算法的性能。我们还证明了我们的框架，将其应用到各种随机组合优化问题，如匹配，拟阵，稳定集问题。
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.