Scheduling appointments online: the power of deferred decision-making
From MaRDI portal
Publication:6176552
DOI10.1007/978-3-031-18367-6_5arXiv2111.13986OpenAlexW3215234994MaRDI QIDQ6176552FDOQ6176552
Authors: Devin Smedira, David B. Shmoys 
Publication date: 25 July 2023
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Abstract: The recently introduced online Minimum Peak Appointment Scheduling (MPAS) problem is a variant of the online bin-packing problem that allows for deferred decision making. Specifically, it allows for the problem to be split into an online phase where a stream of appointment requests arrive requiring a scheduled time, followed by an offline phase where those appointments are scheduled into rooms. Similar to the bin-packing problem, the aim is to use the minimum number of rooms in the final configuration. This model more accurately captures scheduling appointments than bin packing. For example, a dialysis patient needs to know what time to arrive for an appointment, but does not need to know the assigned station ahead of time. Previous work developed a randomized algorithm for this problem which achieved an asymptotic competitive ratio of at most 1.5, proving that online MPAS was fundamentally different from the online bin-packing problem. Our main contribution is to develop a new randomized algorithm for the problem that achieves an asymptotic competitive ratio under 1.455, indicating the potential for further progress. This improvement is attained by modifying the process for scheduling appointments to increase the density of the packing in the worst case, along with utilizing the dual of the bin-packing linear programming relaxation to perform the analysis. We also present the first known lower bound of 1.2 on the asymptotic competitive ratio of both deterministic and randomized online MPAS algorithm. These results demonstrate how deferred decision-making can be leveraged to yield improved worst-case performance, a phenomenon which should be investigated in a broader class of settings.
Full work available at URL: https://arxiv.org/abs/2111.13986
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Algorithmic graph theory and perfect graphs
- A simple on-line bin-packing algorithm
- Fast algorithms for bin packing
- A new lower bound for classic online bin packing
- Does randomization help in on-line bin packing?
- The optimal absolute ratio for online bin packing
- A new and improved algorithm for online bin packing
- Lower bounds on the performance of online algorithms for relaxed packing problems
This page was built for publication: Scheduling appointments online: the power of deferred decision-making
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6176552)
