Online Bin Packing with Predictions

• URL: http://arxiv.org/abs/2102.03311v3
• Date: Wed, 17 Apr 2024 10:25:45 GMT
• Title: Online Bin Packing with Predictions
• Authors: Spyros Angelopoulos, Shahin Kamali, Kimia Shadkami,
• Abstract summary: We study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. We design and analyze online algorithms with efficient tradeoffs between the consistency (i.e., the competitive ratio assuming no prediction error) and the robustness (i.e., the competitive ratio under adversarial error) This is the first theoretical and experimental study of online bin packing under competitive analysis, in the realistic setting of learnable predictions.
• Score: 11.306212771477645
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bin packing is a classic optimization problem with a wide range of applications, from load balancing to supply chain management. In this work, we study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. The online algorithm is enhanced with a (potentially erroneous) prediction concerning the frequency of item sizes in the sequence. We design and analyze online algorithms with efficient tradeoffs between the consistency (i.e., the competitive ratio assuming no prediction error) and the robustness (i.e., the competitive ratio under adversarial error), and whose performance degrades near-optimally as a function of the prediction error. This is the first theoretical and experimental study of online bin packing under competitive analysis, in the realistic setting of learnable predictions. Previous work addressed only extreme cases with respect to the prediction error, and relied on overly powerful and error-free oracles.

Related papers

• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. Prior research in this context was focused on a paradigm where the predictor is pre-trained on past data and then used as a black box. In this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge.
  arXiv  Detail & Related papers  (2024-03-12T08:40:21Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  We consider non-clairvoyant scheduling with online precedence constraints. An algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed.
  arXiv  Detail & Related papers  (2023-01-30T13:17:15Z)
• Online TSP with Predictions [3.8411077568039866]
  We study the classical online traveling salesman problem (OLTSP) Unlike the prediction models in other previous studies, each actual request in the OLTSP, associated with its arrival time and position, may not coincide with the predicted ones. Our main result is to study different prediction models and design algorithms to improve the best-known results in the different settings.
  arXiv  Detail & Related papers  (2022-06-30T15:35:53Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  We introduce a novel measure for quantifying the error in input predictions. The measure captures errors due to absent predicted requests as well as unpredicted actual requests.
  arXiv  Detail & Related papers  (2022-05-25T15:24:03Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
  arXiv  Detail & Related papers  (2022-02-21T13:18:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
  arXiv  Detail & Related papers  (2021-12-10T10:02:31Z)
• Learning-Augmented Algorithms for Online Steiner Tree [14.506230077020994]
  This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms' performance is parameterized by the number of incorrectly predicted terminals. We show that the new online algorithms have strong performance even with modestly correct predictions.
  arXiv  Detail & Related papers  (2021-12-10T06:18:19Z)
• Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms [18.64335888217192]
  We consider online convex optimization with time-varying stage costs and additional switching costs. Since the switching costs introduce coupling across all stages, long-term predictions tend to suffer from lower quality. We introduce a gradient-based online algorithm, Receding Horizon Inexact Gradient (RHIG), and analyze its performance by dynamic regrets.
  arXiv  Detail & Related papers  (2020-11-25T06:25:51Z)
• Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing [12.961453245099044]
  We propose a new model for augmenting algorithms with predictions by requiring that they are formally learnable and instance robust. We design online algorithms with predictions for a network flow allocation problem and restricted assignment makespan minimization.
  arXiv  Detail & Related papers  (2020-11-23T21:38:57Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. The goal is to design algorithms that are both consistent and robust. We provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions.
  arXiv  Detail & Related papers  (2020-10-22T04:51:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.