論文の概要: Pareto-Optimal Learning-Augmented Algorithms for Online k-Search Problems

• arxiv url: http://arxiv.org/abs/2211.06567v1
• Date: Sat, 12 Nov 2022 04:12:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-15 19:52:15.220554
• Title: Pareto-Optimal Learning-Augmented Algorithms for Online k-Search Problems
• Title（参考訳）: オンラインk- Search問題に対するPareto-Optimal Learning-Augmented Algorithms
• Authors: Russell Lee, Bo Sun, John C.S. Lui, Mohammad Hajiesmaili
• Abstract要約: 本稿では,k-maxとk-minの探索問題に対するオンラインアルゴリズムの設計に機械学習による予測を利用する。 我々のアルゴリズムは、予測が正確である場合(すなわち一貫性)にオフラインアルゴリズムと競合する性能を達成することができ、また予測が任意に間違っている場合(すなわち堅牢性)に最悪のケース保証を提供する。
• 参考スコア（独自算出の注目度）: 26.460333932540863
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper leverages machine learned predictions to design online algorithms for the k-max and k-min search problems. Our algorithms can achieve performances competitive with the offline algorithm in hindsight when the predictions are accurate (i.e., consistency) and also provide worst-case guarantees when the predictions are arbitrarily wrong (i.e., robustness). Further, we show that our algorithms have attained the Pareto-optimal trade-off between consistency and robustness, where no other algorithms for k-max or k-min search can improve on the consistency for a given robustness. To demonstrate the performance of our algorithms, we evaluate them in experiments of buying and selling Bitcoin.
• Abstract（参考訳）: 本稿では,k-max および k-min 探索問題に対するオンラインアルゴリズムの設計に機械学習による予測を利用する。 我々のアルゴリズムは、予測が正確である場合(すなわち一貫性)、あるいは予測が任意に間違っている場合(すなわち堅牢性)に、オフラインアルゴリズムと競合する性能を後から得ることができる。 さらに, このアルゴリズムは, k-max や k-min 探索のための他のアルゴリズムが, 与えられたロバスト性の整合性を改善することができないような, 整合性とロバスト性の間のパレート最適トレードオフを達成したことを示す。 アルゴリズムのパフォーマンスを示すために、ビットコインを売買する実験で評価します。

関連論文リスト

• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems [0.0]
  本稿では,オンライン境界割当問題とオンライン広告入札問題に対する機械学習予測を用いたアルゴリズムを提案する。 予測の質に応じて競合性能を達成するアルゴリズムを構築した。
  論文  参考訳（メタデータ） (2024-02-13T13:02:11Z)
• Learning-augmented Online Algorithm for Two-level Ski-rental Problem [8.381344684943212]
  本研究では,3つの支払いオプションのうちの1つを選択することで,複数の項目に対する要求の順序を満たす必要がある2段階のスキーレンタル問題について検討する。 我々は、機械学習予測を頑健なオンラインアルゴリズムに組み込むことにより、学習増強アルゴリズム(LADTSR)を開発した。
  論文  参考訳（メタデータ） (2024-02-09T16:10:54Z)
• Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.029788598491077]
  エネルギーとサステナビリティの交差点で発生した問題を捉えるオンライン問題の一群である,スイッチングコストによるオンライン変換について検討する。 本稿では,この問題の決定論的および決定論的変異に対して,競合的(ロバストな)しきい値に基づくアルゴリズムを導入する。 そこで我々は,ブラックボックスのアドバイスを活かした学習強化アルゴリズムを提案し,平均ケース性能を著しく向上させた。
  論文  参考訳（メタデータ） (2023-10-31T16:34:49Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• 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)
• Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems [13.593621603504847]
  我々は,予測が正確である場合に競争率を改善することを目的として,オンライン変換問題の競合アルゴリズムを設計する。 また、予測品質に関わらず、最悪の競合比率を保証します。 ビットコイン変換に関する数値実験により,OTAの性能を実証した。
  論文  参考訳（メタデータ） (2021-09-03T14:27:33Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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