論文の概要: Approximation Algorithms for Combinatorial Optimization with Predictions

• arxiv url: http://arxiv.org/abs/2411.16600v1
• Date: Mon, 25 Nov 2024 17:31:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-26 14:18:27.210405
• Title: Approximation Algorithms for Combinatorial Optimization with Predictions
• Title（参考訳）: 予測を用いた組合せ最適化のための近似アルゴリズム
• Authors: Antonios Antoniadis, Marek Eliáš, Adam Polak, Moritz Venzin,
• Abstract要約: 従来のアルゴリズムの近似保証よりも高い精度で予測を行う。 我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。 この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
• 参考スコア（独自算出の注目度）: 3.7235228254732524
• License:
• Abstract: We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a systematic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight. This gives simple (near-)linear time algorithms for, e.g., Vertex Cover, Steiner Tree, Min-Weight Perfect Matching, Knapsack, and Clique. Our algorithms produce optimal solutions when provided with perfect predictions and their approximation ratios smoothly degrade with increasing prediction error. With small enough prediction error we achieve approximation guarantees that are beyond reach without predictions in the given time bounds, as exemplified by the NP-hardness and APX-hardness of many of the above problems. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds; we demonstrate this on the Steiner Tree problem. We conclude with an empirical evaluation of our approach.
• Abstract（参考訳）: ランニング時間を増加させることなく,従来のアルゴリズムの近似保証を改善するために予測を利用する体系的な研究を開始する。 本稿では,最小(最大)全重みの入力項目の実行可能なサブセットを選択することを求める,幅広い最適化問題に対する体系的手法を提案する。 これにより、Vertex Cover、Steiner Tree、Min-Weight Perfect Matching、Knapsack、Cliqueなどの単純な(ほぼ)線形時間アルゴリズムが提供される。 提案アルゴリズムは,予測誤差の増大とともに近似比が円滑に低下した場合に最適解を生成する。 十分な予測誤差を小さくすることで、上記の問題の多くにおいてNP硬度とAPX硬度によって示されるように、与えられた時間境界の予測無しに到達可能な近似保証を達成する。 この種の問題に対して,本手法は全体として最適であることを示すが,改良された境界を得るために個々の問題の構造的特性を利用する可能性があり,Steiner Tree問題でこれを実証する。 我々は我々のアプローチの実証的な評価で結論付けた。

関連論文リスト

• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。 我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
  論文  参考訳（メタデータ） (2024-08-07T23:15:21Z)
• Rolling Lookahead Learning for Optimal Classification Trees [0.0]
  本稿では,木構築における最適手法の展望と,ミオピックアプローチの相対的拡張性を組み合わせた転がりサブツリールックアヘッドアルゴリズムを提案する。 提案手法は1330件のうち808件において最適, 筋電図的アプローチよりも優れ, サンプル外精度を最大で23.6%, 14.4%向上した。
  論文  参考訳（メタデータ） (2023-04-21T09:17:00Z)
• Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster $\text{L}$-/$\text{L}^\natural$-Convex Function Minimization [15.191184049312467]
  新たな研究のラインでは、マシンが学習した予測は、二部マッチングのような離散最適化問題に対するアルゴリズムのウォームスタートに有用である。 我々のフレームワークは、予測と全ての最適解の間の距離に比例した境界を提供する。 したがって、複数の最適解によらず、アルゴリズムを確実にウォームスタートさせることができる予測の初回学習性を与える。
  論文  参考訳（メタデータ） (2023-02-02T08:00:18Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives [9.593208961737572]
  本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。 本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。 提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
  論文  参考訳（メタデータ） (2021-04-14T19:21:59Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Stochastic Optimization Forests [60.523606291705214]
  標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。 概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
  論文  参考訳（メタデータ） (2020-08-17T16:56:06Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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