Fugu-MT 論文翻訳(概要): An explicit vector algorithm for high-girth MaxCut

論文の概要: An explicit vector algorithm for high-girth MaxCut

arxiv url: http://arxiv.org/abs/2108.12477v1
Date: Fri, 27 Aug 2021 19:47:56 GMT
ステータス: 処理完了
システム内更新日: 2023-03-17 00:42:32.554033
Title: An explicit vector algorithm for high-girth MaxCut
Title（参考訳）: 高次MaxCutのための明示的ベクトルアルゴリズム
Authors: Jessica K. Thompson, Ojas Parekh, Kunal Marwaha
Abstract要約: すべての$d geq 3$と$k geq 4$に対して、我々の近似保証は著者に知られている他の古典的および量子的アルゴリズムよりも優れている。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We give an approximation algorithm for MaxCut and provide guarantees on the average fraction of edges cut on $d$-regular graphs of girth $\geq 2k$. For every $d \geq 3$ and $k \geq 4$, our approximation guarantees are better than those of all other classical and quantum algorithms known to the authors. Our algorithm constructs an explicit vector solution to the standard semidefinite relaxation of MaxCut and applies hyperplane rounding. It may be viewed as a simplification of the previously best known technique, which approximates Gaussian wave processes on the infinite $d$-regular tree.
Abstract（参考訳）: 我々はmaxcutの近似アルゴリズムを提供し、$d$-regular graphs of girth $\geq 2k$ でカットされた辺の平均分数を保証する。すべての$d \geq 3$と$k \geq 4$に対して、我々の近似保証は他の古典的および量子的アルゴリズムよりも優れている。提案アルゴリズムは,MaxCut の半定次緩和に対する明示的なベクトル解を構築し,超平面丸めを適用した。これは、無限の $d$-正則木上のガウス波過程を近似する、最もよく知られた手法の単純化と見なすことができる。

関連論文リスト

Non-Euclidean High-Order Smooth Convex Optimization [9.940728137241214]
我々は、H"より古い連続$q$-th微分を持つ凸対象の最適化のためのアルゴリズムを、p$-normに対して開発する。他の構造化関数も最適化できる。
論文参考訳（メタデータ） (2024-11-13T19:22:34Z)
A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12:28Z)
A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文参考訳（メタデータ） (2021-10-28T14:19:30Z)
The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
量子近似最適化アルゴリズム (QAOA) は最適化問題の近似解を求める。任意の深さで$D$に対して性能を評価するための反復式を任意の深さ$p$で与える。我々は、QAOAが無限大の$p$でパリの価値を達成できるという楽観的な予想を立てる。
論文参考訳（メタデータ） (2021-10-27T06:35:59Z)
Classical algorithms and quantum limitations for maximum cut on high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。 1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文参考訳（メタデータ） (2021-06-10T16:28:23Z)
Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs [0.0]
すべての次数$D ge 2$ of girth $> 5$に対して、QAOA$はQAOA$ on $G$よりも大きなカット率を持つことを示す。任意の定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在すると推測する。
論文参考訳（メタデータ） (2021-01-14T09:17:20Z)
Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文参考訳（メタデータ） (2020-10-13T17:26:09Z)
Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。ここでの私たちの下限は、ノイズのないケースでも新規です。
論文参考訳（メタデータ） (2020-06-24T04:41:43Z)
Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文参考訳（メタデータ） (2020-04-16T19:16:38Z)

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