Document Open Access Logo

Online Multidimensional Packing Problems in the Random-Order Model

Authors David Naori, Danny Raz

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.10.pdf
  • Filesize: 493 kB
  • 15 pages

Document Identifiers

Author Details

David Naori
  • Computer Science Department, Technion, 32000 Haifa, Israel
Danny Raz
  • Computer Science Department, Technion, 32000 Haifa, Israel

Cite AsGet BibTex

David Naori and Danny Raz. Online Multidimensional Packing Problems in the Random-Order Model. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.10

Abstract

We study online multidimensional variants of the generalized assignment problem which are used to model prominent real-world applications, such as the assignment of virtual machines with multiple resource requirements to physical infrastructure in cloud computing. These problems can be seen as an extension of the well known secretary problem and thus the standard online worst-case model cannot provide any performance guarantee. The prevailing model in this case is the random-order model, which provides a useful realistic and robust alternative. Using this model, we study the d-dimensional generalized assignment problem, where we introduce a novel technique that achieves an O(d)-competitive algorithms and prove a matching lower bound of Omega(d). Furthermore, our algorithm improves upon the best-known competitive-ratio for the online (one-dimensional) generalized assignment problem and the online knapsack problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Online algorithms
Keywords
  • Random Order
  • Generalized Assignment Problem
  • Knapsack Problem
  • Multidimensional Packing
  • Secretary Problem

Metrics

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

References

  1. Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations. In SODA, pages 1253-1264. SIAM, 2011. Google Scholar
  2. Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A Dynamic Near-Optimal Algorithm for Online Linear Programming. Operations Research, 62(4):876-890, 2014. Google Scholar
  3. Yossi Azar, Ilan Reuven Cohen, Seny Kamara, and F. Bruce Shepherd. Tight bounds for online vector bin packing. In STOC, pages 961-970. ACM, 2013. Google Scholar
  4. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A Knapsack Secretary Problem with Applications. In APPROX-RANDOM, volume 4627 of Lecture Notes in Computer Science, pages 16-28. Springer, 2007. Google Scholar
  5. Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In SODA, pages 434-443. SIAM, 2007. Google Scholar
  6. Niv Buchbinder, Kamal Jain, and Mohit Singh. Secretary Problems via Linear Programming. Math. Oper. Res., 39(1):190-206, 2014. Google Scholar
  7. Chandra Chekuri and Sanjeev Khanna. On Multi-Dimensional Packing Problems. In SODA, pages 185-194. ACM/SIAM, 1999. Google Scholar
  8. Henrik I Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24:63-79, 2017. Google Scholar
  9. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Adaptivity and approximation for stochastic packing problems. In SODA, pages 395-404. SIAM, 2005. Google Scholar
  10. Eugene B Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Mathematics, 4:627-629, 1963. Google Scholar
  11. Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Clifford Stein. Online Stochastic Packing Applied to Display Ad Allocation. In ESA (1), volume 6346 of Lecture Notes in Computer Science, pages 182-194. Springer, 2010. Google Scholar
  12. Michael R Garey, Ronald L Graham, David S Johnson, and Andrew Chi-Chih Yao. Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, Series A, 21(3):257-298, 1976. Google Scholar
  13. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. In ESA, volume 8125 of Lecture Notes in Computer Science, pages 589-600. Springer, 2013. Google Scholar
  14. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal Beats Dual on Online Packing LPs in the Random-Order Model. SIAM J. Comput., 47(5):1939-1964, 2018. Google Scholar
  15. Robert D. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In SODA, pages 630-631. SIAM, 2005. Google Scholar
  16. Benny Lehmann, Daniel J. Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270-296, 2006. Google Scholar
  17. Denis V Lindley. Dynamic programming and decision theory. Journal of the Royal Statistical Society: Series C (Applied Statistics), 10(1):39-51, 1961. Google Scholar
  18. Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. AdWords and generalized online matching. J. ACM, 54(5):22, 2007. Google Scholar
  19. Marco Molinaro and R. Ravi. Geometry of Online Packing Linear Programs. In ICALP (1), volume 7391 of Lecture Notes in Computer Science, pages 701-713. Springer, 2012. Google Scholar
  20. Danny Raz, Itai Segall, and Maayan Goldstein. Multidimensional resource allocation in practice. In Proceedings of the 10th ACM International Systems and Storage Conference, page 1. ACM, 2017. Google Scholar
  21. Lei Shi, Bernard Butler, Dmitri Botvich, and Brendan Jennings. Provisioning of requests for virtual machine sets with placement constraints in IaaS clouds. In 2013 IFIP/IEEE International Symposium on Integrated Network Management (IM 2013), pages 499-505. IEEE, 2013. Google Scholar
  22. David Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing, 3(1):103-128, 2007. Google Scholar
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 Imprint Privacy Contact