English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We study the problem of solving Packing Integer Programs (PIPs) in the onlinesetting, where columns in $[0,1]^d$ of the constraint matrix are revealedsequentially, and the goal is to pick a subset of the columns that sum to atmost $B$ in each coordinate while maximizing the objective. Excellent resultsare known in the secretary setting, where the columns are adversarially chosen,but presented in a uniformly random order. However, these existing algorithmsare susceptible to adversarial attacks: they try to "learn" characteristics ofa good solution, but tend to over-fit to the model, and hence a small number ofadversarial corruptions can cause the algorithm to fail.  In this paper, we give the first robust algorithms for Packing IntegerPrograms, specifically in the recently proposed Byzantine Secretary framework.Our techniques are based on a two-level use of online learning, to robustlylearn an approximation to the optimal value, and then to use this robustestimate to pick a good solution. These techniques are general and we use themto design robust algorithms for PIPs in the prophet model as well, specificallyin the Prophet-with-Augmentations framework. We also improve known results inthe Byzantine Secretary framework: we make the non-constructive resultsalgorithmic and improve the existing bounds for single-item and matroidconstraints.

Robust Secretary and Prophet Algorithms for Packing Integer Programs