Document Open Access Logo

Improved Online Algorithms for Knapsack and GAP in the Random Order Model

Authors Susanne Albers, Arindam Khan, Leon Ladewig

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.22.pdf
  • Filesize: 0.6 MB
  • 23 pages

Document Identifiers

Author Details

Susanne Albers
  • Technical University of Munich, Germany
Arindam Khan
  • Indian Institute of Science, Bangalore, India
Leon Ladewig
  • Technical University of Munich, Germany

Funding

Work supported by the European Research Council, Grant Agreement No. 691672.

Cite AsGet BibTex

Susanne Albers, Arindam Khan, and Leon Ladewig. Improved Online Algorithms for Knapsack and GAP in the Random Order Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.22

Abstract

The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set. We develop a randomized (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)]. Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)].

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online algorithms
  • knapsack problem
  • random order model

Metrics

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

References

  1. 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
  2. Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. The Online Stochastic Generalized Assignment Problem. In Proc. 16th International Workshop on Approximation, Randomization, and Combinatorial Optimization and 17th International Workshop on Randomization and Computation (APPROX/RANDOM), pages 11-25, 2013. Google Scholar
  3. Susanne Albers and Leon Ladewig. New results for the k-secretary problem. Unpublished manuscript, 2018. Google Scholar
  4. Moshe Babaioff, Jason Hartline, and Robert Kleinberg. Selling banner ads: Online algorithms with buyback. In Fourth Workshop on Ad Auctions, 2008. Google Scholar
  5. Moshe Babaioff, Jason D. Hartline, and Robert D. Kleinberg. Selling ad campaigns: online algorithms with cancellations. In Proc. 10th ACM Conference on Electronic Commerce (EC), pages 61-70, 2009. Google Scholar
  6. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A Knapsack Secretary Problem with Applications. In Proc. 10th International Workshop on Approximation, Randomization, and Combinatorial Optimization and 11th International Workshop on Randomization and Computation (APPROX/RANDOM), pages 16-28, 2007. Google Scholar
  7. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Matroid Secretary Problems. Journal of the ACM, 65(6):35:1-35:26, 2018. Google Scholar
  8. Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani. A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model. In Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 31-39, 2010. Google Scholar
  9. Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Kamal Jain, Omid Etesami, and Mohammad Mahdian. Dynamics of bid optimization in online advertisement auctions. In Proc. 16th International Conference on World Wide Web (WWW), pages 531-540, 2007. Google Scholar
  10. Niv Buchbinder and Joseph Naor. Online Primal-Dual Algorithms for Covering and Packing. Math. Oper. Res., 34(2):270-286, 2009. Google Scholar
  11. Dirk G. Cattrysse and Luk N. Van Wassenhove. A survey of algorithms for the generalized assignment problem. European Journal of Operational Research, 60(3):260-272, 1992. Google Scholar
  12. T.-H. Hubert Chan, Fei Chen, and Shaofeng H.-C. Jiang. Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1169-1188, 2015. Google Scholar
  13. Chandra Chekuri and Sanjeev Khanna. A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. SIAM Journal on Computing (SICOMP), 35(3):713-728, 2005. Google Scholar
  14. 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
  15. Eugene B Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Mathematics, 4:627-629, 1963. Google Scholar
  16. Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Clifford Stein. Online Stochastic Packing Applied to Display Ad Allocation. In Proc. 18th Annual European Symposium on Algorithms (ESA), pages 182-194, 2010. Google Scholar
  17. Jon Feldman, Nitish Korula, Vahab S. Mirrokni, S. Muthukrishnan, and Martin Pál. Online Ad Assignment with Free Disposal. In Proc. 5th International Workshop Internet and Network Economics (WINE), pages 374-385, 2009. Google Scholar
  18. P.R. Freeman. The secretary problem and its extensions: A review. International Statistical Review/Revue Internationale de Statistique, pages 189-206, 1983. Google Scholar
  19. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating Geometric Knapsack via L-Packings. In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 260-271, 2017. Google Scholar
  20. Oliver Göbel, Thomas Kesselheim, and Andreas Tönnis. Online Appointment Scheduling in the Random Order Model. In Proc. 23rd Annual European Symposium on Algorithms (ESA), pages 680-692, 2015. Google Scholar
  21. Xin Han, Yasushi Kawase, and Kazuhisa Makino. Online Unweighted Knapsack Problem with Removal Cost. Algorithmica, 70(1):76-91, 2014. Google Scholar
  22. Xin Han, Yasushi Kawase, and Kazuhisa Makino. Randomized algorithms for online knapsack problems. Theoretical Computer Science, 562:395-405, 2015. Google Scholar
  23. Kazuo Iwama and Shiro Taketomi. Removable Online Knapsack Problems. In Proc. 29th International Colloquium on Automata, Languages and Programming (ICALP), pages 293-305, 2002. Google Scholar
  24. Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack problems. Springer, 2004. Google Scholar
  25. Claire Kenyon. Best-Fit Bin-Packing with Random Order. In Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 359-364, 1996. Google Scholar
  26. 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 Proc. 21st Annual European Symposium on Algorithms (ESA), pages 589-600, 2013. Google Scholar
  27. 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
  28. Samir Khuller, Stephen G. Mitchell, and Vijay V. Vazirani. On-Line Algorithms for Weighted Bipartite Matching and Stable Marriages. Theoretical Computer Science, 127(2):255-267, 1994. Google Scholar
  29. Robert D. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 630-631, 2005. Google Scholar
  30. Nitish Korula, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order. SIAM J. Comput., 47(3):1056-1086, 2018. Google Scholar
  31. Denis V Lindley. Dynamic programming and decision theory. Applied Statistics, pages 39-51, 1961. Google Scholar
  32. George S. Lueker. Average-Case Analysis of Off-Line and On-Line Knapsack Problems. J. Algorithms, 29(2):277-305, 1998. Google Scholar
  33. Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In Proc. 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 597-606, 2011. Google Scholar
  34. Alberto Marchetti-Spaccamela and Carlo Vercellis. Stochastic on-line knapsack problems. Mathematical Programming, 68:73-104, 1995. Google Scholar
  35. Silvano Martello and Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., New York, NY, USA, 1990. Google Scholar
  36. Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. AdWords and generalized online matching. Journal of the ACM, 54(5):22, 2007. Google Scholar
  37. Adam Meyerson. Online Facility Location. In Proc. 42nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 426-431, 2001. Google Scholar
  38. Vahab S. Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam. Simultaneous approximations for adversarial and stochastic online budgeted allocation. In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1690-1701, 2012. Google Scholar
  39. Marco Molinaro and R. Ravi. The Geometry of Online Packing Linear Programs. Math. Oper. Res., 39(1):46-59, 2014. Google Scholar
  40. ML Nikolaev. On a generalization of the best choice problem. Theory of Probability & Its Applications, 22(1):187-190, 1977. Google Scholar
  41. Temel Öncan. A Survey of the Generalized Assignment Problem and Its Applications. Information Systems and Operational Research INFOR, 45(3):123-141, 2007. Google Scholar
  42. Mitsushi Tamaki. Recognizing both the maximum and the second maximum of a sequence. Journal of Applied Probability, 16(4):803-812, 1979. Google Scholar
  43. Rahul Vaze. Online knapsack problem and budgeted truthful bipartite matching. In Proc. IEEE Conference on Computer Communications (INFOCOM) 2017, pages 1-9, 2017. Google Scholar
  44. Rahul Vaze. Online Knapsack Problem Under Expected Capacity Constraint. In Proc. IEEE Conference on Computer Communications (INFOCOM) 2018, pages 2159-2167, 2018. Google Scholar
  45. Yunhong Zhou, Deeparnab Chakrabarty, and Rajan M. Lukose. Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems. In Proc. 4th International Workshop Internet and Network Economics (WINE), pages 566-576, 2008. 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