論文の概要: Competitive Algorithms for Online Knapsack with Succinct Predictions

• arxiv url: http://arxiv.org/abs/2406.18752v1
• Date: Wed, 26 Jun 2024 20:38:00 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-28 15:56:54.503745
• Title: Competitive Algorithms for Online Knapsack with Succinct Predictions
• Title（参考訳）: アクセント予測を用いたオンラインクナップサックの競合アルゴリズム
• Authors: Mohammadreza Daneshvaramoli, Helia Karisani, Adam Lechowicz, Bo Sun, Cameron Musco, Mohammad Hajiesmaili,
• Abstract要約: オンラインのknapsack問題では、異なる値と重みを持つオンラインで到着するアイテムをキャパシティ限定のknapsackにまとめて、受け入れられたアイテムの総価値を最大化する。 この問題に対するテキスト学習強化アルゴリズムについて検討し、機械学習による予測を用いて悲観的な最悪のケースの保証を超えて行動することを目的とする。
• 参考スコア（独自算出の注目度）: 16.793099279933163
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the online knapsack problem, the goal is to pack items arriving online with different values and weights into a capacity-limited knapsack to maximize the total value of the accepted items. We study \textit{learning-augmented} algorithms for this problem, which aim to use machine-learned predictions to move beyond pessimistic worst-case guarantees. Existing learning-augmented algorithms for online knapsack consider relatively complicated prediction models that give an algorithm substantial information about the input, such as the total weight of items at each value. In practice, such predictions can be error-sensitive and difficult to learn. Motivated by this limitation, we introduce a family of learning-augmented algorithms for online knapsack that use \emph{succinct predictions}. In particular, the machine-learned prediction given to the algorithm is just a single value or interval that estimates the minimum value of any item accepted by an offline optimal solution. By leveraging a relaxation to online \emph{fractional} knapsack, we design algorithms that can leverage such succinct predictions in both the trusted setting (i.e., with perfect prediction) and the untrusted setting, where we prove that a simple meta-algorithm achieves a nearly optimal consistency-robustness trade-off. Empirically, we show that our algorithms significantly outperform baselines that do not use predictions and often outperform algorithms based on more complex prediction models.
• Abstract（参考訳）: オンラインのknapsack問題では、異なる値と重みを持つオンラインで到着するアイテムをキャパシティ限定のknapsackにまとめて、受け入れられたアイテムの総価値を最大化する。 本稿では,機械学習による予測を用いて,悲観的な最悪のケースの保証を超えることを目的とした,この問題に対する‘textit{learning-augmented’アルゴリズムについて検討する。 既存のオンラインknapsackの学習強化アルゴリズムは、各値におけるアイテムの総重量など、入力に関する実質的な情報を与えるアルゴリズムを与える比較的複雑な予測モデルを考える。 実際には、そのような予測は誤りに敏感であり、学習が困難である。 この制限により、オンラインのknapsackに「emph{succinct predictions}」を用いた学習強化アルゴリズムのファミリーを導入する。 特に、アルゴリズムに与えられた機械学習予測は、オフライン最適解によって受け入れられる任意のアイテムの最小値を推定する単一の値またはインターバルである。 オンライン「emph{fractional} knapsack」への緩和を利用して、信頼された設定(つまり完璧な予測)と信頼できない設定の両方でそのような簡潔な予測を活用できるアルゴリズムを設計する。 経験的に、我々のアルゴリズムは予測を使わないベースラインを著しく上回り、より複雑な予測モデルに基づいてアルゴリズムを上回ります。

関連論文リスト

• 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)

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

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