Fugu-MT 論文翻訳(概要): Learning-Augmented Algorithms for the Bahncard Problem

論文の概要: Learning-Augmented Algorithms for the Bahncard Problem

arxiv url: http://arxiv.org/abs/2410.15257v1
Date: Sun, 20 Oct 2024 02:55:15 GMT
ステータス: 翻訳完了
システム内更新日: 2024-10-22 13:15:43.733187
Title: Learning-Augmented Algorithms for the Bahncard Problem
Title（参考訳）: Bahncard問題に対する学習強化アルゴリズム
Authors: Hailiang Zhao, Xueyan Tang, Peng Chen, Shuiguang Deng,
Abstract要約: 本研究では,Bahncard問題に対する学習強化アルゴリズムについて検討する。 PFSUMは、オンライン意思決定を改善するために、歴史と短期の両方を取り入れている。
参考スコア（独自算出の注目度）: 12.852098444482426
License:
Abstract: In this paper, we study learning-augmented algorithms for the Bahncard problem. The Bahncard problem is a generalization of the ski-rental problem, where a traveler needs to irrevocably and repeatedly decide between a cheap short-term solution and an expensive long-term one with an unknown future. Even though the problem is canonical, only a primal-dual-based learning-augmented algorithm was explicitly designed for it. We develop a new learning-augmented algorithm, named PFSUM, that incorporates both history and short-term future to improve online decision making. We derive the competitive ratio of PFSUM as a function of the prediction error and conduct extensive experiments to show that PFSUM outperforms the primal-dual-based algorithm.
Abstract（参考訳）: 本稿では,Bahncard問題に対する学習強化アルゴリズムについて検討する。バーンカード問題(Bahncard problem)は、旅行者が安価な短期ソリューションと高価な長期ソリューションを不確実かつ繰り返し決定する必要があるスキーレンタル問題の一般化である。問題は標準的とはいえ、このアルゴリズムのために設計されたのは、原始的二元学習によるアルゴリズムのみである。我々は,オンライン意思決定を改善するために,歴史と短期の両方を取り入れた学習強化アルゴリズム PFSUM を開発した。予測誤差の関数として PFSUM の競合比を導出し,PFSUM が原始双対アルゴリズムより優れていることを示す広範な実験を行った。

関連論文リスト

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)
Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis [0.1529342790344802]
マルチオプションスキーレンタル問題に対する学習向上アルゴリズムを提案する。提案アルゴリズムは,この問題に対して最も有効なランダム化競合アルゴリズムに基づいている。
論文参考訳（メタデータ） (2023-02-14T05:05:03Z)
Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文参考訳（メタデータ） (2023-01-30T13:17:15Z)
Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文参考訳（メタデータ） (2021-11-23T18:10:48Z)
Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds [38.80523710193321]
複数の省電力状態を持つシステムにおける電力消費を最小化するオンライン問題について検討する。アルゴリズムは、異なるエネルギー消費と覚醒コストの省電力状態を選択する必要がある。アイドル期間の予測長に基づいて(潜在的に不正確な)決定を行う学習強化オンラインアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-10-25T17:14:20Z)
Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文参考訳（メタデータ） (2021-09-13T18:10:52Z)
Robust Learning-Augmented Caching: An Experimental Study [8.962235853317996]
キャッシュにおける鍵となる最適化問題は、将来を知ることなく最適に解決できない。学習強化アルゴリズムの新しい分野は、古典的なオンラインキャッシュアルゴリズムを活用するソリューションを提案する。簡単な手法は、高い性能の予測器よりも低いオーバーヘッドしか持たないことを示す。
論文参考訳（メタデータ） (2021-06-28T13:15:07Z)
Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文参考訳（メタデータ） (2021-01-08T18:55:07Z)
Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文参考訳（メタデータ） (2020-07-01T18:43:32Z)
Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文参考訳（メタデータ） (2020-05-09T02:48:23Z)

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