We study the problem of solving Packing Integer Programs (PIPs) in the online setting, where columns in $[0,1]^d$ of the constraint matrix are revealed sequentially, and the goal is to pick a subset of the columns that sum to at most $B$ in 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. 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. 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.
翻译:我们研究在网上设置中解决包装 Integer 程序(PIPs)的问题,在网上设置中,限制矩阵的 $[0,1,1,d$] 列的柱子会按顺序披露,目标是在每一个坐标中挑选一个小栏子,最多等于$B$,同时最大限度地实现目标。在秘书设置中,各栏是对抗性选择的,但以统一的随机顺序呈现出优异的结果。然而,这些现有算法很容易受到对抗性攻击:它们试图“清除”一个好解决方案的特征,但往往过于适合模型,因此,少数对抗性腐败可能导致算法失败。在本文中,我们为包装 Integer 程序提供了第一批强健的算法,特别是在最近提议的Byzantine 秘书框架中。我们的技术基于两级的在线学习,强有力地学习对最佳价值的近似值,然后使用这种稳健的估计来选择一个好的解决办法。这些技术是一般的,我们用它们来为预想模型中的PIPs设计稳健的算法,我们用这些方法可以导致算法失败。在预言型模型中,具体地改进了我们所知道的预想式框架。