論文の概要: Simulated Annealing is a Polynomial-Time Approximation Scheme for the
Minimum Spanning Tree Problem
- arxiv url: http://arxiv.org/abs/2204.02097v2
- Date: Sat, 22 Jul 2023 10:11:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-26 01:20:20.545028
- Title: Simulated Annealing is a Polynomial-Time Approximation Scheme for the
Minimum Spanning Tree Problem
- Title（参考訳）: シミュレート・アニーリングは最小スパンディングツリー問題に対する多項式時間近似スキームである
- Authors: Benjamin Doerr and Amirhossein Rajabi and Carsten Witt
- Abstract要約: 我々は、シミュレートされたアニーリングが、時間内の最小スパンニングツリー問題に対して、任意に厳密な定数係数近似を計算することを証明した。
任意の$epsilon>0$に対して、$O((mnln(n))1+1/epsilon+o(1)(lnln n + ln(T_0/w_min))$を少なくとも1-1/m$の確率で選ぶことができる。
- 参考スコア（独自算出の注目度）: 8.34061303235504
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove that Simulated Annealing with an appropriate cooling schedule
computes arbitrarily tight constant-factor approximations to the minimum
spanning tree problem in polynomial time. This result was conjectured by
Wegener (2005). More precisely, denoting by $n, m, w_{\max}$, and $w_{\min}$
the number of vertices and edges as well as the maximum and minimum edge weight
of the MST instance, we prove that simulated annealing with initial temperature
$T_0 \ge w_{\max}$ and multiplicative cooling schedule with factor $1-1/\ell$,
where $\ell = \omega (mn\ln(m))$, with probability at least $1-1/m$ computes in
time $O(\ell (\ln\ln (\ell) + \ln(T_0/w_{\min}) ))$ a spanning tree with weight
at most $1+\kappa$ times the optimum weight, where $1+\kappa =
\frac{(1+o(1))\ln(\ell m)}{\ln(\ell) -\ln (mn\ln (m))}$. Consequently, for any
$\epsilon>0$, we can choose $\ell$ in such a way that a
$(1+\epsilon)$-approximation is found in time
$O((mn\ln(n))^{1+1/\epsilon+o(1)}(\ln\ln n + \ln(T_0/w_{\min})))$ with
probability at least $1-1/m$. In the special case of so-called
$(1+\epsilon)$-separated weights, this algorithm computes an optimal solution
(again in time $O( (mn\ln(n))^{1+1/\epsilon+o(1)}(\ln\ln n +
\ln(T_0/w_{\min})))$), which is a significant speed-up over Wegener's runtime
guarantee of $O(m^{8 + 8/\epsilon})$.
- Abstract（参考訳）: 適切な冷却スケジュールを持つシミュレートアニーリングは、多項式時間で最小スパンディングツリー問題に対する任意にタイトな定数要素近似を計算する。
この結果は Wegener (2005) によって予想された。
より正確には、$n, m, w_{\max}$ および $w_{\min}$ の頂点と辺の個数と MST インスタンスの最大および最小エッジ重量とで表すと、初期温度$T_0 \ge w_{\max}$ と 1-1/\ell$ の乗算冷却スケジュールでアニーリングをシミュレートし、$\ell = \omega (mn\ln) で表すことができる。
(m))$, 確率 1-1/m$ 計算時間 $O(\ell (\ln\ln (\ell) + \ln(T_0/w_{\min})))$ 1+\kappa$ 1+\kappa = \frac{(1+o(1))\ln(\ell)
m)}{\ln(\ell) -\ln (mn\ln)
(m))}$。
したがって、$\epsilon>0$ の場合、$(1+\epsilon)$-approximation がtime $O((mn\ln) で見つかるような方法で $\ell$ を選択することができる。
(n))^{1+1/\epsilon+o(1)}(\ln\ln n + \ln(t_0/w_{\min}))) 確率は少なくとも 1-1/m$ である。
いわゆる$(1+\epsilon)$-分離重みの特別な場合、このアルゴリズムは最適な解(時間$o((mn\ln)) を計算する。
(n))^{1+1/\epsilon+o(1)}(\ln\ln n + \ln(t_0/w_{\min}))$) これはwegenerのランタイムの$o(m^{8 + 8/\epsilon})$に対する大きなスピードアップである。
関連論文リスト
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - On the Complexity of Finite-Sum Smooth Optimization under the
Polyak-{\L}ojasiewicz Condition [14.781921087738967]
本稿では、$min_bf xinmathbb Rd f(bf x)triangleq frac1nsum_i=1n f_i(bf x)$, ここで、$f(cdot)$はパラメータ$mu$と$f_i(cdot)_i=1n$は$L$-mean-squared smoothである。
論文 参考訳（メタデータ） (2024-02-04T17:14:53Z) - Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function
Approximation: Minimax Optimal and Instance-Dependent Regret Bounds [26.277745106128197]
本研究では,線形関数近似を用いた強化学習におけるそのような報奨の課題に対処する。
我々はまず,重み付き線形包帯に対するtextscHeavy-OFUL というアルゴリズムを設計し,インセンス依存の$T$-round regret of $tildeObig を実現した。
我々の結果は、オンライン回帰問題全般において、重くノイズを扱うことに独立した関心を持つような、新しい自己正規化集中不等式によって達成される。
論文 参考訳（メタデータ） (2023-06-12T02:56:09Z) - An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。
我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文 参考訳（メタデータ） (2022-12-29T19:26:12Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。
重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-02T05:26:10Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。