論文の概要: Online Bin Packing with Predictions
- arxiv url: http://arxiv.org/abs/2102.03311v1
- Date: Fri, 5 Feb 2021 17:32:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-08 12:52:09.101419
- Title: Online Bin Packing with Predictions
- Title(参考訳): 予測付きオンラインビンパッキング
- Authors: Spyros Angelopoulos and Shahin Kamali and Kimia Shadkami
- Abstract要約: 様々なサイズの項目の列を、一様容量のビンの最小限の個数に配置しなければならない問題について、オンライン版について検討する。
オンラインアルゴリズムは、シーケンス内のアイテムサイズの頻度に関する(潜在的に誤った)予測で拡張される。
- 参考スコア(独自算出の注目度): 2.3204178451683264
- 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 in networks 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 their
consistency (i.e., the competitive ratio assuming no prediction error) and
their robustness (i.e., the competitive ratio under adversarial error), and
whose performance degrades gently as a function of the error. Previous work on
this problem has only addressed the extreme cases with respect to the
prediction error, and has relied on overly powerful and error-free prediction
oracles.
- Abstract(参考訳): ビンパッキングは、ネットワークのロードバランシングからサプライチェーン管理まで、幅広いアプリケーションを備えた古典的な最適化問題です。
本研究では,様々なサイズの項目の列を,容量が一様である最小のビン数に配置しなければならない,問題のオンライン変種について検討する。
オンラインアルゴリズムは、シーケンス内のアイテムサイズの頻度に関する(潜在的に誤った)予測で拡張される。
整合性(予測誤差のない競合比率)と堅牢性(敵対誤差下の競争比率)を効率的にトレードオフし、その性能がエラーの関数として穏やかに低下するオンラインアルゴリズムを設計・分析します。
この問題に対する以前の取り組みは、予測エラーに関する極端なケースのみに対処し、過度に強力でエラーのない予測オラクルに依存してきた。
関連論文リスト
- Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。
アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文 参考訳(メタデータ) (2023-01-30T13:17:15Z) - A Universal Error Measure for Input Predictions Applied to Online Graph
Problems [57.58926849872494]
本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。
この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
論文 参考訳(メタデータ) (2022-05-25T15:24:03Z) - 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) - CPNet: Cross-Parallel Network for Efficient Anomaly Detection [20.84973451610082]
ここでは、性能低下を伴わない計算を最小化するために、効率的な異常検出のためのクロスパラレルネットワーク(CPNet)を提案する。
ネットワーク間シフトモジュールは、シーケンシャルフレーム間の時間的関係をキャプチャして、より正確な将来の予測を可能にする。
論文 参考訳(メタデータ) (2021-08-10T05:29:37Z) - Online Adversarial Attacks [57.448101834579624]
我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。
まず、オンライン脅威モデルの決定論的変種を厳格に分析する。
このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
論文 参考訳(メタデータ) (2021-03-02T20:36:04Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳(メタデータ) (2021-03-02T11:04:33Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。