_:n21f71838e43942f38d198d09f388ebdexb26
<http://schema.org/description>
"The random-order or secretary model is one of the most popular beyond-worst\ncase model for online algorithms. While it avoids the pessimism of the\ntraditional adversarial model, in practice we cannot expect the input to be\npresented in perfectly random order. This has motivated research on “best of\nboth worlds” (algorithms with good performance on both purely stochastic and\npurely adversarial inputs), or even better, on inputs that are a mix of both\nstochastic and adversarial parts. Unfortunately the latter seems much harder to\nachieve and very few results of this type are known.\n  Towards advancing our understanding of designing such robust algorithms, we\npropose a random-order model with bursts of adversarial time steps. The\nassumption of burstiness of unexpected patterns is reasonable in many contexts,\nsince changes (e.g. spike in a demand for a good) are often triggered by a\ncommon external event. We then consider the Knapsack Secretary problem in this\nmodel: there is a knapsack of size k (e.g., available quantity of a good),\nand in each of the n time steps an item comes with its value and size in\n[0,1] and the algorithm needs to make an irrevocable decision whether to\naccept or reject the item.\n  We design an algorithm that gives an approximation of 1 -\nÕ(Γ/k) when the adversarial time steps can be covered by Γ≥√(k) intervals of size Õ(n/k). In particular,\nsetting Γ = √(k) gives a (1 - O(ln^2\nk/√(k)))-approximation that is resistant to up to a ln^2\nk/√(k)-fraction of the items being adversarial, which is almost optimal\neven in the absence of adversarial items. Also, setting Γ =\nΩ̃(k) gives a constant approximation that is resistant to up to a\nconstant fraction of items being adversarial."
<https://api.deepai.org/profile/thomas-kesselheim>