論文の概要: Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice

• arxiv url: http://arxiv.org/abs/2002.05808v2
• Date: Fri, 23 Oct 2020 00:49:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-01 13:47:34.456060
• Title: Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice
• Title（参考訳）: 機械学習によるマルチショップスキーレンタルのオンラインアルゴリズム
• Authors: Shufan Wang, Jian Li, Shiqiang Wang
• Abstract要約: 本稿では,機械学習(ML)によるオンラインアルゴリズムの強化問題について検討する。 特に,古典的スキーレンタル問題の一般化であるエンフルティショップスキーレンタル(MSSR)問題を考える。 我々は、決定に1つまたは複数のML予測を使用する場合、決定論的およびランダム化されたオンラインアルゴリズムの両方の性能を確実に向上させる。
• 参考スコア（独自算出の注目度）: 14.139763648079537
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of augmenting online algorithms with machine learned (ML) advice. In particular, we consider the \emph{multi-shop ski rental} (MSSR) problem, which is a generalization of the classical ski rental problem. In MSSR, each shop has different prices for buying and renting a pair of skis, and a skier has to make decisions on when and where to buy. We obtain both deterministic and randomized online algorithms with provably improved performance when either a single or multiple ML predictions are used to make decisions. These online algorithms have no knowledge about the quality or the prediction error type of the ML prediction. The performance of these online algorithms are robust to the poor performance of the predictors, but improve with better predictions. Extensive experiments using both synthetic and real world data traces verify our theoretical observations and show better performance against algorithms that purely rely on online decision making.
• Abstract（参考訳）: 機械学習(ML)によるオンラインアルゴリズムの強化問題について検討する。 特に,古典的なスキーレンタル問題を一般化した「emph{multi-shop ski rent} (MSSR)」問題を考える。 mssrでは、各店舗はスキーの購入とレンタルの料金が異なるため、スキーヤーはいつどこで購入するかを決定する必要がある。 我々は、決定に1つまたは複数のML予測を使用する場合、決定論的およびランダム化されたオンラインアルゴリズムの両方の性能を確実に向上させる。 これらのオンラインアルゴリズムは、ML予測の品質や予測エラータイプについて知識を持たない。 これらのオンラインアルゴリズムのパフォーマンスは、予測器の貧弱な性能に対して堅牢であるが、より良い予測により改善されている。 合成データと実世界のデータトレースの両方を用いた広範な実験は、我々の理論的観察を検証し、純粋にオンライン意思決定に依存するアルゴリズムに対する優れた性能を示す。

関連論文リスト

• Improving Online Algorithms via ML Predictions [19.03466073202238]
  我々は,スキーレンタルと非好ましくないジョブスケジューリングの2つの古典的問題を考察し,予測を用いて意思決定を行う新しいオンラインアルゴリズムを得る。 これらのアルゴリズムは予測器の性能を損なうものであり、より良い予測で改善するが、予測が貧弱な場合はあまり劣化しない。
  論文  参考訳（メタデータ） (2024-07-25T02:17:53Z)
• Learning-augmented Online Algorithm for Two-level Ski-rental Problem [8.381344684943212]
  本研究では,3つの支払いオプションのうちの1つを選択することで,複数の項目に対する要求の順序を満たす必要がある2段階のスキーレンタル問題について検討する。 我々は、機械学習予測を頑健なオンラインアルゴリズムに組み込むことにより、学習増強アルゴリズム(LADTSR)を開発した。
  論文  参考訳（メタデータ） (2024-02-09T16:10:54Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis [0.1529342790344802]
  マルチオプションスキーレンタル問題に対する学習向上アルゴリズムを提案する。 提案アルゴリズムは,この問題に対して最も有効なランダム化競合アルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2023-02-14T05:05:03Z)
• Memory Bounds for the Experts Problem [53.67419690563877]
  専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。 目標は、予測を処理し、最小コストで予測を行うことです。 アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
  論文  参考訳（メタデータ） (2022-04-21T01:22:18Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds [38.80523710193321]
  複数の省電力状態を持つシステムにおける電力消費を最小化するオンライン問題について検討する。 アルゴリズムは、異なるエネルギー消費と覚醒コストの省電力状態を選択する必要がある。 アイドル期間の予測長に基づいて(潜在的に不正確な)決定を行う学習強化オンラインアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-10-25T17:14:20Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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