Fugu-MT 論文翻訳(概要): Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems

論文の概要: Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems

arxiv url: http://arxiv.org/abs/2406.18752v2
Date: Wed, 09 Jul 2025 14:20:53 GMT
ステータス: 翻訳完了
システム内更新日: 2025-07-10 17:37:43.211414
Title: Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems
Title（参考訳）: 学習強化オンラインクナップサック問題に対する準最適一貫性-ロバスト性トレードオフ
Authors: Mohammadreza Daneshvaramoli, Helia Karisani, Adam Lechowicz, Bo Sun, Cameron Musco, Mohammad Hajiesmaili,
Abstract要約: 本稿では,オンラインknapsack問題に対する学習強化アルゴリズムのファミリーを紹介する。本稿では,オンラインアルゴリズム設計における新たな洞察を提供する新しい分数変換手法を提案する。
参考スコア（独自算出の注目度）: 16.793099279933163
License: http://creativecommons.org/licenses/by/4.0/
Abstract: This paper introduces a family of learning-augmented algorithms for online knapsack problems that achieve near Pareto-optimal consistency-robustness trade-offs through a simple combination of trusted learning-augmented and worst-case algorithms. Our approach relies on succinct, practical predictions -- single values or intervals estimating the minimum value of any item in an offline solution. Additionally, we propose a novel fractional-to-integral conversion procedure, offering new insights for online algorithm design.
Abstract（参考訳）: 本稿では,オンラインクナップサック問題に対する学習強化アルゴリズムの一群について紹介する。我々のアプローチは簡潔で実践的な予測に依存します -- オフラインソリューションにおけるアイテムの最小値を見積もる単一値やインターバルです。さらに,オンラインアルゴリズム設計における新たな洞察を提供する新しい分数変換手法を提案する。

関連論文リスト

Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
従来のアルゴリズムの近似保証よりも高い精度で予測を行う。我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
論文参考訳（メタデータ） (2024-11-25T17:31:34Z)
Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
論文参考訳（メタデータ） (2024-03-12T08:40:21Z)
Algorithms with Prediction Portfolios [23.703372221079306]
我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
論文参考訳（メタデータ） (2022-10-22T12:58:07Z)
Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
論文参考訳（メタデータ） (2022-02-22T18:37:23Z)
Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文参考訳（メタデータ） (2022-02-21T13:18:11Z)
Learning Predictions for Algorithms with Predictions [49.341241064279714]
予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
論文参考訳（メタデータ） (2022-02-18T17:25:43Z)
Parsimonious Learning-Augmented Caching [29.975391787684966]
本稿では,学習補助アルゴリズムが同時に予測を利用できるような設定を導入し,研究する。定量的に類似した結果が得られるが、予測のサブ線形数のみを用いることを示す。
論文参考訳（メタデータ） (2022-02-09T03:40:11Z)
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)

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