文章基本信息

标题：Knapsack Secretary with Bursty Adversary
本地全文：下载
作者：Thomas Kesselheim ; Marco Molinaro
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：72:1-72:15
DOI：10.4230/LIPIcs.ICALP.2020.72
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The random-order or secretary model is one of the most popular beyond-worst case model for online algorithms. While this model avoids the pessimism of the traditional adversarial model, in practice we cannot expect the input to be presented in perfectly random order. This has motivated research on best of both worlds (algorithms with good performance on both purely stochastic and purely adversarial inputs), or even better, on inputs that are a mix of both stochastic and adversarial parts. Unfortunately the latter seems much harder to achieve and very few results of this type are known. Towards advancing our understanding of designing such robust algorithms, we propose a random-order model with bursts of adversarial time steps. The assumption of burstiness of unexpected patterns is reasonable in many contexts, since changes (e.g. spike in a demand for a good) are often triggered by a common external event. We then consider the Knapsack Secretary problem in this model: there is a knapsack of size k (e.g., available quantity of a good), and in each of the n time steps an item comes with its value and size in [0,1] and the algorithm needs to make an irrevocable decision whether to accept or reject the item. We design an algorithm that gives an approximation of 1 - OÌf(Î"/k) when the adversarial time steps can be covered by Î" â¥ â^Sk intervals of size OÌf(n/k). In particular, setting Î" = â^Sk gives a (1 - O((lnÂ² k)/â^Sk))-approximation that is resistant to up to a (ln k)/â^Sk-fraction of the items being adversarial, which is almost optimal even in the absence of adversarial items. Also, setting Î" = Î©Ìf(k) gives a constant approximation that is resistant to up to a constant fraction of items being adversarial. While the algorithm is a simple "primal" one it does not possess the crucial symmetry properties exploited in the traditional analyses. The strategy of our analysis is more robust and significantly different from previous ones, and we hope it can be useful for other beyond-worst-case models.
关键词：Beyond worst-case; secretary problem; random order; online algorithms; knapsack