TY - GEN

T1 - Robust Secretary and Prophet Algorithms for Packing Integer Programs

AU - Argue, C. J.

AU - Gupta, Anupam

AU - Molinaro, Marco

AU - Singla, Sahil

N1 - Publisher Copyright:
© 2022 Association for Computing Machinery. All rights reserved.

PY - 2022

Y1 - 2022

N2 - 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-t 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.

AB - 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-t 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.

UR - http://www.scopus.com/inward/record.url?scp=85130759165&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85130759165&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85130759165

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1273

EP - 1297

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

PB - Association for Computing Machinery

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Y2 - 9 January 2022 through 12 January 2022

ER -