論文の概要: Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis

• arxiv url: http://arxiv.org/abs/2302.06832v1
• Date: Tue, 14 Feb 2023 05:05:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-15 16:18:57.659653
• Title: Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis
• Title（参考訳）: 最適競合解析によるマルチオプションスキーレンタル問題の学習提示アルゴリズムの改善
• Authors: Yongho Shin, Changyeol Lee, Gukryeol Lee, Hyung-Chan An
• Abstract要約: マルチオプションスキーレンタル問題に対する学習向上アルゴリズムを提案する。 提案アルゴリズムは,この問題に対して最も有効なランダム化競合アルゴリズムに基づいている。
• 参考スコア（独自算出の注目度）: 0.1529342790344802
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper, we present improved learning-augmented algorithms for the multi-option ski rental problem. Learning-augmented algorithms take ML predictions as an added part of the input and incorporates these predictions in solving the given problem. Due to their unique strength that combines the power of ML predictions with rigorous performance guarantees, they have been extensively studied in the context of online optimization problems. Even though ski rental problems are one of the canonical problems in the field of online optimization, only deterministic algorithms were previously known for multi-option ski rental, with or without learning augmentation. We present the first randomized learning-augmented algorithm for this problem, surpassing previous performance guarantees given by deterministic algorithms. Our learning-augmented algorithm is based on a new, provably best-possible randomized competitive algorithm for the problem. Our results are further complemented by lower bounds for deterministic and randomized algorithms, and computational experiments evaluating our algorithms' performance improvements.
• Abstract（参考訳）: 本稿では,マルチオプションスキーレンタル問題に対する学習向上アルゴリズムを提案する。 学習強化アルゴリズムは、ML予測を入力の付加部分として取り、これらの予測を与えられた問題を解決するために組み込む。 ML予測のパワーと厳格な性能保証を組み合わせた独自の強みにより、オンライン最適化問題の文脈で広く研究されている。 スキーレンタル問題は、オンライン最適化の分野における標準的な問題の1つであるが、以前はマルチオプションスキーレンタルで知られていたのは決定論的アルゴリズムのみであり、拡張学習の有無であった。 本稿では、決定論的アルゴリズムによる従来の性能保証を上回って、この問題に対する最初のランダム化学習型アルゴリズムを提案する。 学習提示型アルゴリズムは,問題に対する新しい予測可能な最善のランダム化アルゴリズムに基づいている。 さらに, 決定論的およびランダム化アルゴリズムの下位境界と, アルゴリズムの性能改善を評価する計算実験により, 結果をさらに補完する。

関連論文リスト

• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental [0.0]
  学習強化型マルチオプションスキーレンタル問題は、古典的なスキーレンタル問題を2つの方法で一般化する。 ランダム化アルゴリズムでは、一貫性-ロバスト性トレードオフに対する最初の非自明な下界を示す。 私たちのアルゴリズムは、一貫性が 1.086 であるとき、e/2 の係数の範囲内のロバスト性に対する低い境界と一致します。
  論文  参考訳（メタデータ） (2023-12-05T07:33:51Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。 HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
  論文  参考訳（メタデータ） (2022-10-31T14:06:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Benchmarking Feature-based Algorithm Selection Systems for Black-box Numerical Optimization [0.0]
  特徴に基づくアルゴリズムの選択は、目に見えない問題において最適化アルゴリズムのポートフォリオから最適なアルゴリズムを自動的に見つけることを目的としている。 本稿では,24個のノイズレスブラックボックス最適化ベンチマーク関数のアルゴリズム選択システムについて分析する。 アルゴリズム選択システムの性能は, 逐次最小二乗プログラミングをプリゾルバとして利用することにより, 大幅に向上できることを示す。
  論文  参考訳（メタデータ） (2021-09-17T07:17:40Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• The Primal-Dual method for Learning Augmented Algorithms [10.2730668356857]
  我々は、オンラインアルゴリズムの原始二重法を拡張し、次のアクションについてオンラインアルゴリズムにアドバイスする予測を組み込む。 我々のアルゴリズムは、予測が正確である場合にも、予測が誤解を招くとき、適切な保証を維持しながら、どのオンラインアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-22T11:58:47Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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