Online Learning for Min Sum Set Cover and Pandora's Box
Online Learning for Min Sum Set Cover and Pandora's Box
复制标题
在线学习 Min Sum Set Cover 和潘多拉魔盒
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Christos Tzamos
中科院分区：
文献类型：
--
作者：
Evangelia Gergatsouli;Christos Tzamos
随机优化中的两个核心问题是最小和集覆盖和潘多拉盒子。在潘多拉盒子中，我们有$n$个盒子，每个盒子都包含一个未知值，我们的目标是以某种顺序打开盒子，以最小化搜索成本和找到的最小值之和。给定值向量的分布，我们被要求确定一个接近最优的搜索顺序。“最小和集覆盖”对应于值为0或无穷大的情况。在这项工作中，我们研究的情况下，值向量不是从一个分布，但在一个在线的方式呈现给学习者。我们提出了一个计算效率高的算法，是恒定的竞争力对成本的最佳搜索顺序。我们将我们的结果扩展到一个强盗设置，其中只有打开的盒子的值在每一轮之后才显示给学习者。我们还将我们的结果推广到其他常用的潘多拉盒子和最小和集覆盖，涉及选择一个以上的值受到拟阵约束的研究变种。
Two central problems in Stochastic Optimization are Min Sum Set Cover and Pandora's Box. In Pandora's Box, we are presented with $n$ boxes, each containing an unknown value and the goal is to open the boxes in some order to minimize the sum of the search cost and the smallest value found. Given a distribution of value vectors, we are asked to identify a near-optimal search order. Min Sum Set Cover corresponds to the case where values are either 0 or infinity. In this work, we study the case where the value vectors are not drawn from a distribution but are presented to a learner in an online fashion. We present a computationally efficient algorithm that is constant-competitive against the cost of the optimal search order. We extend our results to a bandit setting where only the values of the boxes opened are revealed to the learner after every round. We also generalize our results to other commonly studied variants of Pandora's Box and Min Sum Set Cover that involve selecting more than a single value subject to a matroid constraint.
拟阵上的子模随机探测
DOI：
10.4230/lipics.stacs.2014.29
发表时间：
2014
期刊：
--
影响因子：
--
作者：
Adamczyk M
通讯作者：
Adamczyk M
组合划分问题的算法配置的学习理论基础
DOI：
10.48550/arxiv.1611.04535
发表时间：
2016
期刊：
arXiv e-prints
影响因子：
--
作者：
Balcan Maria-Florina
通讯作者：
Balcan Maria-Florina