論文の概要: Online Bin Packing with Predictions

• arxiv url: http://arxiv.org/abs/2102.03311v3
• Date: Wed, 17 Apr 2024 10:25:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-19 00:31:27.999778
• Title: Online Bin Packing with Predictions
• Title（参考訳）: 予測付きオンラインビンパッキング
• Authors: Spyros Angelopoulos, Shahin Kamali, Kimia Shadkami,
• Abstract要約: 様々なサイズの項目の列を、一様容量のビンの最小限の個数に配置しなければならない問題について、オンライン版について検討する。 我々は、一貫性(すなわち、予測誤差を仮定しない競争比)と堅牢性(すなわち、逆誤差の下での競争比)の間の効率的なトレードオフを持つオンラインアルゴリズムを設計し、分析する。 これは、学習可能な予測の現実的な設定において、競争分析の下でのオンラインビンパッキングに関する最初の理論的、実験的研究である。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: Bin Packingは、ロードバランシングからサプライチェーン管理に至るまで、幅広いアプリケーションにおいて古典的な最適化問題である。 本研究では,様々なサイズの項目の列を,一様容量のビンの最小個数に配置しなければならない問題のオンライン版について検討する。 オンラインアルゴリズムは、シーケンス内のアイテムサイズの頻度に関する(潜在的に誤った)予測で拡張される。 我々は、一貫性(すなわち、予測誤差を仮定しない競合比)と堅牢性(すなわち、逆誤差の下での競合比)との間の効率的なトレードオフを持つオンラインアルゴリズムを設計し、分析し、予測誤差の関数としてほぼ最適に性能が低下する。 これは、学習可能な予測の現実的な設定において、競争分析の下でのオンラインビンパッキングに関する最初の理論的、実験的研究である。 これまでの作業は、予測エラーに関して極端なケースにのみ対処し、過度に強力でエラーのないオラクルに依存していた。

関連論文リスト

• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Online TSP with Predictions [3.8411077568039866]
  古典的オンライン旅行セールスマン問題(OLTSP)について検討する。 他の研究の予測モデルとは異なり、OLTSPの実際の要求はその到着時間と位置に関連しており、予測された要求と一致しないかもしれない。 我々の主な成果は、様々な予測モデルと設計アルゴリズムを研究し、異なる設定で最もよく知られた結果を改善することである。
  論文  参考訳（メタデータ） (2022-06-30T15:35:53Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。 この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
  論文  参考訳（メタデータ） (2022-05-25T15:24:03Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Learning-Augmented Algorithms for Online Steiner Tree [14.506230077020994]
  本稿では,どの端末がオンラインにやってくるかを予測するアルゴリズムについて考察する。 予測は誤りであり、アルゴリズムのパフォーマンスは誤って予測された端末の数によってパラメータ化される。 新たなオンラインアルゴリズムは,適度に正確な予測でも高い性能を示す。
  論文  参考訳（メタデータ） (2021-12-10T06:18:19Z)
• Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms [18.64335888217192]
  オンライン凸最適化は、時間的変化のあるステージコストと追加のスイッチングコストで検討する。 スイッチングコストはすべてのステージにカップリングをもたらすため、長期的な予測は品質の低下に悩まされる傾向がある。 本稿では,勾配に基づくオンラインアルゴリズムReceding Horizon Inexact Gradient (RHIG)を導入し,その性能を動的後悔によって解析する。
  論文  参考訳（メタデータ） (2020-11-25T06:25:51Z)
• Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing [12.961453245099044]
  本稿では,アルゴリズムが形式的に学習可能で,例えば頑健であることを要求して,予測を伴うアルゴリズムの拡張モデルを提案する。 ネットワークフロー割当問題と制限された割当ミスパン最小化の予測を含むオンラインアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-11-23T21:38:57Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。