Document Open Access Logo

Knapsack Secretary with Bursty Adversary

Authors Thomas Kesselheim, Marco Molinaro

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.72.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Thomas Kesselheim
  • University of Bonn, Germany
Marco Molinaro
  • PUC-Rio, Rio de Janeiro, Brazil

Funding

This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing.
  • Molinaro, Marco: MM was supported by CNPq grants Universal #431480/2016-8 and Bolsa de Produtividade em Pesquisa #310516/2017-0, FAPERJ grant Jovem Cientista do Nosso Estado, and a Microsoft Research Fellowship at the Simons Institute for the Theory of Computing.

Cite As Get BibTex

Thomas Kesselheim and Marco Molinaro. Knapsack Secretary with Bursty Adversary. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.72

Abstract

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 - Õ(Γ/k) when the adversarial time steps can be covered by Γ ≥ √k intervals of size Õ(n/k). In particular, setting Γ = √k gives a (1 - O((ln² k)/√k))-approximation that is resistant to up to a (ln k)/√k-fraction of the items being adversarial, which is almost optimal even in the absence of adversarial items. Also, setting Γ = Ω̃(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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Beyond worst-case
  • secretary problem
  • random order
  • online algorithms
  • knapsack

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Shipra Agrawal and Nikhil R. Devanur. Fast algorithms for online stochastic convex programming. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1405-1424, 2015. URL: https://doi.org/10.1137/1.9781611973730.93.
  2. Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research, 62(4):876-890, 2014. URL: https://doi.org/10.1287/opre.2014.1289.
  3. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In APPROX-RANDOM, 2007. Google Scholar
  4. Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 434-443, 2007. Google Scholar
  5. Domagoj Bradac, Anupam Gupta, Sahil Singla, and Goran Zuzic. Robust algorithms for the secretary problem. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 32:1-32:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.32.
  6. Sourav Chakraborty and Oded Lachish. Improved competitive ratio for the matroid secretary problem. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1702-1712, 2012. URL: https://doi.org/10.1137/1.9781611973099.135.
  7. G.R. Dattatreya. Performance Analysis of Queuing and Computer Networks (Chapman & Hall/Crc Computer & Information Science Series). Chapman & Hall/CRC, 2008. Google Scholar
  8. Nikhil R. Devanur and Thomas P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In EC, 2009. Google Scholar
  9. Qiming Diao, Jing Jiang, Feida Zhu, and Ee-Peng Lim. Finding bursty topics from microblogs. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers - Volume 1, ACL '12, pages 536-544, 2012. Google Scholar
  10. Devdatt Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1st edition, 2009. Google Scholar
  11. Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni. Online allocation with traffic spikes: Mixing adversarial and stochastic models. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, pages 169-186, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2764468.2764536.
  12. Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Clifford Stein. Online stochastic packing applied to display ad allocation. In ESA, 2010. Google Scholar
  13. Moran Feldman, Ola Svensson, and Rico Zenklusen. A simple o(log log(rank))-competitive algorithm for the matroid secretary problem. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15, pages 1189-1201, 2015. Google Scholar
  14. Moran Feldman, Ola Svensson, and Rico Zenklusen. A framework for the secretary problem on the intersection of matroids. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 735-752, 2018. Google Scholar
  15. Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pages 1562-1578, 2019. URL: http://proceedings.mlr.press/v99/gupta19a.html.
  16. Anupam Gupta and Marco Molinaro. How the experts algorithm can help solve lps online. Mathematics of Operations Research, 41(4):1404-1431, 2016. URL: https://doi.org/10.1287/moor.2016.0782.
  17. Thomas Kesselheim, Robert D. Kleinberg, and Rad Niazadeh. Secretary problems with non-uniform arrival order. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 879-888, 2015. URL: https://doi.org/10.1145/2746539.2746602.
  18. Thomas Kesselheim, Andreas Tönnis, Klaus Radke, and Berthold Vöcking. Primal beats dual on online packing lps in the random-order model. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC '14, pages 303-312, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2591796.2591810.
  19. Jon Kleinberg. Bursty and hierarchical structure in streams. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '02, pages 91-101, New York, NY, USA, 2002. ACM. URL: https://doi.org/10.1145/775047.775061.
  20. Jon Kleinberg, Yuval Rabani, and Éva Tardos. Allocating bandwidth for bursty connections. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 664-673, New York, NY, USA, 1997. ACM. URL: https://doi.org/10.1145/258533.258661.
  21. Robert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In SODA, 2005. Google Scholar
  22. Nitish Korula, Vahab Mirrokni, and Morteza Zadimoghaddam. Online submodular welfare maximization: Greedy beats 1/2 in random order. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '15, pages 889-898, 2015. URL: https://doi.org/10.1145/2746539.2746626.
  23. O. Lachish. O(log log rank) competitive ratio for the matroid secretary problem. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 326-335, October 2014. URL: https://doi.org/10.1109/FOCS.2014.42.
  24. Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. In STOC 2018, 2018. Google Scholar
  25. A. Meyerson. Online facility location. In Proceedings of the 42Nd IEEE Symposium on Foundations of Computer Science, FOCS '01, pages 426-431, Washington, DC, USA, 2001. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=874063.875567.
  26. Vahab S. Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam. Simultaneous approximations for adversarial and stochastic online budgeted allocation. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 1690-1701, 2012. Google Scholar
  27. Marco Molinaro. Online and random-order load balancing simultaneously. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 1638-1650, 2017. Google Scholar
  28. Marco Molinaro and R. Ravi. Geometry of online packing linear programs. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming, pages 701-713, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  29. Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, pages 1287-1295, 2014. URL: http://proceedings.mlr.press/v32/seldinb14.html.
  30. Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, pages 467-475, 2019. URL: http://proceedings.mlr.press/v89/zimmert19a.html.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact