論文の概要: Learning Augmented Exact Exponential Algorithms

• arxiv url: http://arxiv.org/abs/2606.18807v1
• Date: Wed, 17 Jun 2026 08:23:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-18 17:16:51.065072
• Title: Learning Augmented Exact Exponential Algorithms
• Title（参考訳）: 拡張された排他的アルゴリズムの学習
• Authors: Tatiana Belova, Yuriy Dementiev, Danil Sagunov,
• Abstract要約: 探索空間を確実に減らすのに、ランダムな推測に勝る雑音の多い予測器が十分であることを示す。 我々のアルゴリズムは、予測のペア独立性のみを必要とするか、あるいは、予測者の正確性に関する知識を必要としない。
• 参考スコア（独自算出の注目度）: 3.0614165499580768
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, the focus has been almost exclusively on polynomial-time algorithms, where predictions improve competitive ratios, approximation guarantees, or running times. In this paper, we raise the question of whether predictions can push the frontier of exact exponential-time algorithms for NP-hard problems. We answer this question affirmatively by proposing a general approach that augments an entire family of state-of-the-art exact algorithms for a variety of subset selection problems. We show that a noisy predictor that is only marginally better than random guessing suffices to provably reduce the search space, and that the resulting runtime speedup scales smoothly with the prediction quality. Importantly, our algorithms require only pairwise independence of predictions or, alternatively, do not require the knowledge of the predictor's accuracy - both strictly weaker and more realistic settings than typically assumed.
• Abstract（参考訳）: 学習強化アルゴリズムの分野は、機械学習による予測が、様々な問題にまたがる最悪の下位境界を回避できることを実証している。 しかし、これまでは多項式時間アルゴリズムのみに焦点が当てられており、予測は競合率、近似保証、実行時間を改善する。 本稿では,NP-hard問題に対する厳密な指数時間アルゴリズムのフロンティアを推し進めることができるかという問題を提起する。 我々は、様々なサブセット選択問題に対して、最先端の正確なアルゴリズムのファミリー全体を拡大する一般的なアプローチを提案することで、この疑問に肯定的に答える。 探索空間を確実に減らすためにランダムな推測精度よりもわずかに良い雑音予測器を示し、その結果のランタイムスピードアップは予測品質とともに円滑にスケールすることを示した。 重要なことは、我々のアルゴリズムは予測のペア独立しか必要とせず、代わりに予測者の正確さの知識は必要としない。

関連論文リスト

• Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
  従来のアルゴリズムの近似保証よりも高い精度で予測を行う。 我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。 この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
  論文  参考訳（メタデータ） (2024-11-25T17:31:34Z)
• Improved Frequency Estimation Algorithms with and without Predictions [22.382900492405938]
  データストリームに現れる要素の頻度を推定することは、大規模データ分析において重要なタスクである。 理論的には,Hsu等の学習に基づくアルゴリズムを,予測を使わずに上回る新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-12T18:59:06Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。 これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
  論文  参考訳（メタデータ） (2022-10-22T12:58:07Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。 本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。 実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
  論文  参考訳（メタデータ） (2022-02-22T18:37:23Z)
• 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)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• 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)

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

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