Fugu-MT 論文翻訳(概要): Parameterized Complexity Analysis of Randomized Search Heuristics

論文の概要: Parameterized Complexity Analysis of Randomized Search Heuristics

arxiv url: http://arxiv.org/abs/2001.05120v1
Date: Wed, 15 Jan 2020 03:43:56 GMT
ステータス: 処理完了
システム内更新日: 2023-01-11 06:06:09.674634
Title: Parameterized Complexity Analysis of Randomized Search Heuristics
Title（参考訳）: ランダム化探索ヒューリスティックスのパラメータ化複雑性解析
Authors: Frank Neumann and Andrew M. Sutton
Abstract要約: この章では、ランダム化アルゴリズムのパラメータ化実行時間解析の理論を適用した多数の結果をまとめた。 NP-hard最適化問題の解法を課題とするランダム化検索の集合に対する主な結果と証明手法について概説する。
参考スコア（独自算出の注目度）: 16.759797540118665
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This chapter compiles a number of results that apply the theory of parameterized algorithmics to the running-time analysis of randomized search heuristics such as evolutionary algorithms. The parameterized approach articulates the running time of algorithms solving combinatorial problems in finer detail than traditional approaches from classical complexity theory. We outline the main results and proof techniques for a collection of randomized search heuristics tasked to solve NP-hard combinatorial optimization problems such as finding a minimum vertex cover in a graph, finding a maximum leaf spanning tree in a graph, and the traveling salesperson problem.
Abstract（参考訳）: この章は、パラメータ化アルゴリズムの理論を進化アルゴリズムのようなランダム化探索ヒューリスティックの実行時間解析に適用する多くの結果をまとめている。パラメータ化アプローチは、古典的複雑性理論の従来のアプローチよりも詳細に組合せ問題を解くアルゴリズムの実行時間を特徴付ける。本稿では, グラフ内の頂点被覆の最小化, グラフ内の葉面積の最大化, 旅行セールスパーソン問題など, NPハードな組合せ最適化問題を解くために, ランダム化された探索ヒューリスティックの集合と証明手法について概説する。

関連論文リスト

Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文参考訳（メタデータ） (2023-02-24T18:41:48Z)
Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。決定集合の低次元構造を高次元問題に活用する。
論文参考訳（メタデータ） (2022-11-21T18:31:43Z)
Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。予測と高い確率で、新しい過剰なリスク境界を提供する。我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文参考訳（メタデータ） (2022-11-03T12:40:24Z)
Greedy Relaxations of the Sparsest Permutation Algorithm [4.125187280299247]
我々は, 忠実性よりもますます弱い仮定の下で, 効率的かつ点的に整合したアルゴリズム, GRaSP のクラスを開発する。 GRaSPの最も緩和された形式は、シミュレーションにおいて多くの最先端の因果探索アルゴリズムより優れている。
論文参考訳（メタデータ） (2022-06-11T05:00:36Z)
Run Time Analysis for Random Local Search on Generalized Majority Functions [1.0965065178451106]
我々は、その性質の1つ、中立性がランダムな局所探索の実行時間にどのように影響するかを研究する。我々は、多くの最適化アルゴリズムに適用可能な定理を提案し、MAJORITYの実行時間と対称バージョンHASMAJORITYをリンクする。
論文参考訳（メタデータ） (2022-04-27T08:40:33Z)
Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文参考訳（メタデータ） (2021-06-09T08:05:36Z)
Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-07T08:00:02Z)
Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文参考訳（メタデータ） (2020-12-11T08:28:51Z)
Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems [0.6882042556551609]
このアプローチでは,問題インスタンスの探索空間木を探索するアルゴリズムを用いる。このアルゴリズムはモンテカルロ木探索(Monte Carlo tree search)をベースとしている。
論文参考訳（メタデータ） (2020-10-22T08:33:58Z)
A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem [2.099922236065961]
本稿では, RGA とショート・パス・ツリー・アルゴリズム (SPTA) の主な特徴を組み合わせたクラスタ・ショート・パス・ツリー問題 (CluSPT) を扱うアルゴリズムを提案する。提案アルゴリズムの性能を評価するため,ユークリッドベンチマークが選択される。
論文参考訳（メタデータ） (2020-05-05T08:34:58Z)
Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文参考訳（メタデータ） (2020-02-21T17:45:32Z)

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