論文の概要: Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management

• arxiv url: http://arxiv.org/abs/2604.26349v1
• Date: Wed, 29 Apr 2026 07:00:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-30 15:59:36.282972
• Title: Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
• Title（参考訳）: FIFOバッファ管理のための漸近的ロバスト学習強化アルゴリズム
• Authors: Wen-Han Hsieh, Ya-Chun Liang,
• Abstract要約: FIFOバッファ管理問題に対する学習強化オンラインアルゴリズムを提案する。 本アルゴリズムは, 予測誤差の増加とともに, 最適な1の競合比を同時に達成し, 任意の不正確な予測の下では, sqrt3の競合比を維持する。
• 参考スコア（独自算出の注目度）: 0.6875312133832078
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a learning-augmented online algorithm for the preemptive FIFO buffer management problem, where packets arrive online to a finite-capacity buffer, must be transmitted in FIFO order, and the algorithm may preemptively discard buffered packets to accommodate future arrivals. Our algorithm simultaneously achieves 1-consistency, η-smoothness, and asymptotic \sqrt{3}-robustness, where ηdenotes the prediction error. Specifically, it attains an optimal competitive ratio of 1 under perfect predictions, degrades smoothly as the prediction error increases, and maintains an asymptotic competitive ratio of \sqrt{3} under arbitrarily inaccurate predictions, matching the best-known worst-case guarantee for the classical online problem, established by Englert and Westermann in 2009 [Algorithmica 53(4): 523-548]. A key technical contribution of our work is the introduction of an \emph{output-based prediction error metric}. Because capacity constraints dictate that only a strictly bounded subset of arriving packets is ultimately transmitted, our metric assesses prediction quality over the resulting optimal schedules rather than the raw input sequences, avoiding artificial error penalties. To guarantee robustness, our algorithm dynamically monitors predictions and executes a \emph{buffer-clearing strategy} upon transitioning to a worst-case fallback mechanism. We prove that the competitive loss incurred by this clearing operation is bounded by an additive capacity constant that vanishes asymptotically. Finally, we show that our algorithm provides a generalized framework for learning-augmented buffer management: substituting the fallback module with any β-competitive online algorithm immediately yields asymptotic β-robustness.
• Abstract（参考訳）: 本稿では,有限容量バッファにパケットがオンラインに届き,FIFOの順序で送信されなければならないプリエンプティブFIFOバッファ管理問題に対する学習強化オンラインアルゴリズムを提案する。 提案アルゴリズムは, 1-一貫性, η-smoothness, および漸近的な \sqrt{3}-robustness を同時に達成する。 具体的には、2009年にエングルトとヴェスターマンによって確立された古典的オンライン問題に対する最もよく知られた最悪の保証と一致するように、予測誤差が増大するにつれて、最適な1の競争比率を達成し、漸近的な競争率である \sqrt{3} を任意に不正確な予測の下で維持する(Algorithmica 53(4): 523-548]。 私たちの研究の重要な技術的貢献は、emph{output-based prediction error metric}の導入です。 キャパシティ制約は、到着パケットの厳密な有界部分だけが最終的に送信されることを規定するので、我々の測定基準は、生の入力シーケンスよりも結果の最適スケジュールよりも予測品質を評価することができ、人工的なエラーの罰則を回避することができる。 堅牢性を保証するため,アルゴリズムは予測を動的に監視し,最悪のフォールバック機構に移行する際に「emph{buffer-clearing strategy」を実行する。 このクリアリング演算によって生じる競合損失は、漸近的に消滅する加算容量定数によって境界づけられていることを証明する。 最後に、我々のアルゴリズムは、学習強化バッファ管理のための一般化されたフレームワークを提供しており、任意のβ競合オンラインアルゴリズムでフォールバックモジュールを置換すると、すぐに漸近的なβ-ロバスト性が得られることを示す。

関連論文リスト

• Constrained Online Convex Optimization with Memory and Predictions [9.387819018679325]
  制約付きオンライン凸最適化(COCO-M)について検討し、損失と制約は学習者による過去の意思決定の限られた窓に依存している。 この設定は、以前研究された制約のないオンライン最適化をメモリフレームワークで拡張し、制約された動的システムの制御や再構成予算によるスケジューリングといった実践的な問題を捉えている。
  論文  参考訳（メタデータ） (2026-03-22T19:27:28Z)
• A Switching Framework for Online Interval Scheduling with Predictions [4.352962539265558]
  我々は、各区間を即時に受け入れるか、到着時に拒否しなければならない、取り消し不能な環境でのオンライン区間スケジューリングについて検討する。 我々は,この問題を,アルゴリズムが(機械学習による)予測にアクセスできる学習拡張環境で考える。 私たちの主な貢献はSemiTrust-and-Switchフレームワークであり、予測ベースと古典的間隔スケジューリングアルゴリズムを組み合わせた統一的なアプローチを提供する。
  論文  参考訳（メタデータ） (2025-11-20T10:01:09Z)
• The Coverage Principle: How Pre-Training Enables Post-Training [70.25788947586297]
  予備学習が最終モデルの成功をどう形作るかを検討する。 下流の性能予測におけるカバレッジのパワーを説明するメカニズムを明らかにする。
  論文  参考訳（メタデータ） (2025-10-16T17:53:50Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。 この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
  論文  参考訳（メタデータ） (2022-05-25T15:24:03Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。 本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。 実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
  論文  参考訳（メタデータ） (2022-02-22T18:37:23Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Learning Optimal Power Flow: Worst-Case Guarantees for Neural Networks [1.8352113484137629]
  我々は混合整数線形プログラムを定式化し、ニューラルネットワーク予測の最悪の保証を得る。 従来手法で計算された経験的下限よりも,最悪の場合の保証が1桁も大きいことを示す。
  論文  参考訳（メタデータ） (2020-06-19T09:19:14Z)

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

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