Robust Secretary and Prophet Algorithms for Packing Integer Programs
Robust Secretary and Prophet Algorithms for Packing Integer Programs
复制标题
用于打包整数程序的鲁棒秘书和先知算法
DOI：
10.1137/1.9781611977073.53
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Singla, Sahil
中科院分区：
文献类型：
--
作者：
Argue, C. J.;Gupta, Anupam;Molinaro, Marco;Singla, Sahil
我们研究在线环境中求解打包整数程序 (PIP) 的问题，其中约束矩阵 [0, 1]d 中的列按顺序显示，目标是在最大化目标的同时选择每个坐标总和最多为 B 的列子集。在秘书环境中，效果非常好，其中的列是对抗性选择的，但以统一的随机顺序呈现。然而，这些现有的算法很容易受到对抗性攻击：它们试图“学习”良好解决方案的特征，但往往会过度拟合模型，因此少量的对抗性损坏可能会导致算法失败。在本文中，我们给出了第一个用于打包整数程序的鲁棒算法，特别是在最近提出的拜占庭秘书框架[BGSZ20]中。我们的技术基于在线学习的两级使用，稳健地学习最佳值的近似值，然后使用这种稳健的估计来选择一个好的解决方案。这些技术是通用的，我们也使用它们为预言家模型中的 PIP 设计强大的算法，特别是在预言家增强框架 [ISW20] 中。我们还改进了拜占庭秘书框架中的已知结果：我们使非建设性结果变得算法化，并改进了单项和拟阵约束的现有界限。
We study the problem of solving Packing Integer Programs (PIPs) in the online setting, where columns in [0, 1]dof the constraint matrix are revealed sequentially, and the goal is to pick a subset of the columns that sum to at mostBin each coordinate while maximizing the objective. Excellent results are known in the secretary setting, where the columns are adversarially chosen, but presented in a uniformly random order. However, these existing algorithms are susceptible to adversarial attacks: they try to “learn” characteristics of a good solution, but tend to over-fit to the model, and hence a small number of adversarial corruptions can cause the algorithm to fail.In this paper, we give the first robust algorithms for Packing Integer Programs, specifically in the recently proposed Byzantine Secretary framework [BGSZ20]. Our techniques are based on a two-level use of online learning, to robustly learn an approximation to the optimal value, and then to use this robust estimate to pick a good solution. These techniques are general and we use them to design robust algorithms for PIPs in the prophet model as well, specifically in the Prophet-with-Augmentations framework [ISW20]. We also improve known results in the Byzantine Secretary framework: we make the non-constructive results algorithmic and improve the existing bounds for single-item and matroid constraints.
登录
查看更多内容
影响因子：
2.3
作者：
E. Samuel-Cahn
通讯作者：
E. Samuel-Cahn
DOI：
10.1145/3313276.3316313
发表时间：
2018
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
N. Bansal
通讯作者：
N. Bansal
对抗性注入下的鲁棒算法
DOI：
--
发表时间：
2020
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Paritosh Garg;S. Kale;Lars Rohwedder;O. Svensson
通讯作者：
O. Svensson
DOI：
10.1137/1.9781611973730.79
发表时间：
2014-04
期刊：
Math. Oper. Res.
影响因子：
--
作者：
Moran Feldman;O. Svensson;R. Zenklusen
通讯作者：
Moran Feldman;O. Svensson;R. Zenklusen
随机顺序模型
DOI：
--
发表时间：
2020
期刊：
Beyond the Worst-Case Analysis of Algorithms
影响因子：
--
作者：
Anupam Gupta;Sahil Singla
通讯作者：
Sahil Singla