論文の概要: Learning-augmented Online Algorithm for Two-level Ski-rental Problem

• arxiv url: http://arxiv.org/abs/2402.06715v1
• Date: Fri, 9 Feb 2024 16:10:54 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-13 19:46:04.185607
• Title: Learning-augmented Online Algorithm for Two-level Ski-rental Problem
• Title（参考訳）: 2段階スキーレンタル問題に対する学習強化オンラインアルゴリズム
• Authors: Keyuan Zhang, Zhongdong Liu, Nakjung Choi, Bo Ji
• Abstract要約: 本研究では,3つの支払いオプションのうちの1つを選択することで,複数の項目に対する要求の順序を満たす必要がある2段階のスキーレンタル問題について検討する。 我々は、機械学習予測を頑健なオンラインアルゴリズムに組み込むことにより、学習増強アルゴリズム(LADTSR)を開発した。
• 参考スコア（独自算出の注目度）: 8.381344684943212
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the two-level ski-rental problem,where a user needs to fulfill a sequence of demands for multiple items by choosing one of the three payment options: paying for the on-demand usage (i.e., rent), buying individual items (i.e., single purchase), and buying all the items (i.e., combo purchase). Without knowing future demands, the user aims to minimize the total cost (i.e., the sum of the rental, single purchase, and combo purchase costs) by balancing the trade-off between the expensive upfront costs (for purchase) and the potential future expenses (for rent). We first design a robust online algorithm (RDTSR) that offers a worst-case performance guarantee. While online algorithms are robust against the worst-case scenarios, they are often overly cautious and thus suffer a poor average performance in typical scenarios. On the other hand, Machine Learning (ML) algorithms typically show promising average performance in various applications but lack worst-case performance guarantees. To harness the benefits of both methods, we develop a learning-augmented algorithm (LADTSR) by integrating ML predictions into the robust online algorithm, which outperforms the robust online algorithm under accurate predictions while ensuring worst-case performance guarantees even when predictions are inaccurate. Finally, we conduct numerical experiments on both synthetic and real-world trace data to corroborate the effectiveness of our approach.
• Abstract（参考訳）: 本稿では,オンデマンド利用(家賃)の支払い,個々のアイテムの購入(単一購入),すべてのアイテムの購入(コンボ購入)という3つの支払いオプションの1つを選択することで,ユーザが複数のアイテムに対する要求の連続を満たさなければならない2段階のスキーレンタル問題について検討する。 ユーザは、将来の需要を知らずに、高価な先行コスト(購入)と潜在的将来のコスト(レンタル)とのトレードオフをバランスさせることで、総コスト(レンタル、単価、コンボ購入コストの合計)を最小化することを目指している。 まず、最悪のパフォーマンス保証を提供する堅牢なオンラインアルゴリズム(RDTSR)を設計する。 オンラインアルゴリズムは最悪のシナリオに対して堅牢だが、しばしば過度に慎重であり、典型的なシナリオでは平均的なパフォーマンスを損なう。 一方、機械学習(ML)アルゴリズムは通常、様々なアプリケーションで期待できる平均性能を示すが、最悪のパフォーマンス保証がない。 両手法の利点を生かし,ML予測を頑健なオンラインアルゴリズムに統合し,予測が不正確であっても最悪の性能保証を確保しつつ,頑健なオンラインアルゴリズムを精度よく予測する学習拡張アルゴリズム(LADTSR)を開発した。 最後に,本手法の有効性を相関させるため,合成および実世界のトレースデータの数値実験を行った。

関連論文リスト

• Learning-augmented Online Minimization of Age of Information and Transmission Costs [24.873041306990288]
  我々は,送信コストと安定化コストの合計を最小化し,最悪の性能保証を実現するために,オンラインアルゴリズムを開発した。 オンラインアルゴリズムは堅牢だが、概して保守的であり、典型的なシナリオでは平均的なパフォーマンスが劣っている。 学習強化アルゴリズムは一貫性と堅牢性の両方を達成することを示す。
  論文  参考訳（メタデータ） (2024-03-05T01:06:25Z)
• Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.582885296330195]
  エネルギーとサステナビリティの交差点で発生した問題を捉えるオンライン問題の一群である,スイッチングコストによるオンライン変換について検討する。 本稿では,この問題の決定論的および決定論的変異に対して,競合的(ロバストな)しきい値に基づくアルゴリズムを導入する。 そこで我々は,ブラックボックスのアドバイスを活かした学習強化アルゴリズムを提案し,平均ケース性能を著しく向上させた。
  論文  参考訳（メタデータ） (2023-10-31T16:34:49Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。 このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。 上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
  論文  参考訳（メタデータ） (2023-02-02T16:30:33Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets [32.50099216716867]
  本稿では、揮発性電力市場におけるエネルギー取引のための学習強化アルゴリズムを開発する。 オンライン検索問題に対する競合アルゴリズムの設計には,機械学習による予測が組み込まれている。
  論文  参考訳（メタデータ） (2022-11-12T04:12:10Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)
• Cost-Efficient Online Hyperparameter Optimization [94.60924644778558]
  実験の単一実行でヒトのエキスパートレベルのパフォーマンスに達するオンラインHPOアルゴリズムを提案します。 提案するオンラインhpoアルゴリズムは,実験の1回で人間のエキスパートレベルのパフォーマンスに到達できるが,通常のトレーニングに比べて計算オーバーヘッドは少ない。
  論文  参考訳（メタデータ） (2021-01-17T04:55:30Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)
• Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice [14.139763648079537]
  本稿では,機械学習(ML)によるオンラインアルゴリズムの強化問題について検討する。 特に,古典的スキーレンタル問題の一般化であるエンフルティショップスキーレンタル(MSSR)問題を考える。 我々は、決定に1つまたは複数のML予測を使用する場合、決定論的およびランダム化されたオンラインアルゴリズムの両方の性能を確実に向上させる。
  論文  参考訳（メタデータ） (2020-02-13T22:59:36Z)

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

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