[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Uniform Loss Algorithms for Online Stochastic Decision-Making With Applications to Bin Packing

Published: 09 July 2020 Publication History

Abstract

We consider a general class of finite-horizon online decision-making problems, where in each period a controller is presented a stochastic arrival and must choose an action from a set of permissible actions, and the final objective depends only on the aggregate type-action counts. Such a framework encapsulates many online stochastic variants of common optimization problems including bin packing, generalized assignment, and network revenue management. In such settings, we study a natural model-predictive control algorithm that in each period, acts greedily based on an updated certainty-equivalent optimization problem. We introduce a simple, yet general, condition under which this algorithm obtains uniform additive loss (independent of the horizon) compared to an optimal solution with full knowledge of arrivals. Our condition is fulfilled by the above-mentioned problems, as well as more general settings involving piece-wise linear objectives and offline index policies, including an airline overbooking problem.

References

[1]
Alessandro Arlotto and Itai Gurvich. Uniformly bounded regret in the multisecretary problem. Stochastic Systems, 2019.
[2]
Janos Csirik, David S Johnson, Claire Kenyon, James B Orlin, Peter W Shor, and Richard R Weber. On the sum-of-squares algorithm for bin packing. Journal of the ACM (JACM), 53(1):1--65, 2006.
[3]
Varun Gupta and Ana Radovanovic. Lagrangian-based online stochastic bin packing. In ACM SIGMETRICS Performance Evaluation Review, volume 43, pages 467--468. ACM, 2015.
[4]
Alberto Vera and Siddhartha Banerjee. The bayesian prophet: A low-regret framework for online decision making. In Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, pages 81--82. ACM, 2019.
  1. Uniform Loss Algorithms for Online Stochastic Decision-Making With Applications to Bin Packing

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM SIGMETRICS Performance Evaluation Review
    ACM SIGMETRICS Performance Evaluation Review  Volume 48, Issue 1
    June 2020
    110 pages
    ISSN:0163-5999
    DOI:10.1145/3410048
    Issue’s Table of Contents
    Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 09 July 2020
    Published in SIGMETRICS Volume 48, Issue 1

    Check for updates

    Author Tags

    1. approximate dynamic programming
    2. model-predictive control
    3. online bin packing
    4. online stochastic decision-making

    Qualifiers

    • Research-article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 33
      Total Downloads
    • Downloads (Last 12 months)3
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 31 Dec 2024

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media