論文の概要: Finding the KT partition of a weighted graph in near-linear time
- arxiv url: http://arxiv.org/abs/2111.01378v1
- Date: Tue, 2 Nov 2021 05:26:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-09 09:09:51.100449
- Title: Finding the KT partition of a weighted graph in near-linear time
- Title（参考訳）: 準線形時間における重み付きグラフのKT分割の探索
- Authors: Simon Apers, Pawe{\l} Gawrychowski, Troy Lee
- Abstract要約: カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。
重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 1.572727650614088
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In a breakthrough work, Kawarabayashi and Thorup (J.~ACM'19) gave a
near-linear time deterministic algorithm for minimum cut in a simple graph $G =
(V,E)$. A key component is finding the $(1+\varepsilon)$-KT partition of $G$,
the coarsest partition $\{P_1, \ldots, P_k\}$ of $V$ such that for every
non-trivial $(1+\varepsilon)$-near minimum cut with sides $\{S, \bar{S}\}$ it
holds that $P_i$ is contained in either $S$ or $\bar{S}$, for $i=1, \ldots, k$.
Here we give a near-linear time randomized algorithm to find the
$(1+\varepsilon)$-KT partition of a weighted graph. Our algorithm is quite
different from that of Kawarabayashi and Thorup and builds on Karger's
framework of tree-respecting cuts (J.~ACM'00).
We describe applications of the algorithm. (i) The algorithm makes progress
towards a more efficient algorithm for constructing the polygon representation
of the set of near-minimum cuts in a graph. This is a generalization of the
cactus representation initially described by Bencz\'ur (FOCS'95). (ii) We
improve the time complexity of a recent quantum algorithm for minimum cut in a
simple graph in the adjacency list model from $\widetilde O(n^{3/2})$ to
$\widetilde O(\sqrt{mn})$. (iii) We describe a new type of randomized algorithm
for minimum cut in simple graphs with complexity $O(m + n \log^6 n)$. For
slightly dense graphs this matches the complexity of the current best $O(m + n
\log^2 n)$ algorithm which uses a different approach based on random
contractions.
The key technical contribution of our work is the following. Given a weighted
graph $G$ with $m$ edges and a spanning tree $T$, consider the graph $H$ whose
nodes are the edges of $T$, and where there is an edge between two nodes of $H$
iff the corresponding 2-respecting cut of $T$ is a non-trivial near-minimum cut
of $G$. We give a $O(m \log^4 n)$ time deterministic algorithm to compute a
spanning forest of $H$.
- Abstract（参考訳）: 画期的な研究で、Kawarabayashi と Thorup (J.~ACM'19) は、単純なグラフ $G = (V,E)$ の最小カットに対するほぼ線形時間決定論的アルゴリズムを与えた。
キーコンポーネントは$g$の$(1+\varepsilon)$-ktパーティションを見つけることであるが、最も粗いパーティション$\{p_1, \ldots, p_k\}$ of $v$ であり、すべての非自明な$(1+\varepsilon)$-nearの最小カットに対して$\{s, \bar{s}$ は$s$ または $\bar{s}$、$i=1, \ldots, k$ に含まれている。
ここでは、重み付きグラフの$(1+\varepsilon)$-KTパーティションを見つけるために、ほぼ線形な時間ランダム化アルゴリズムを与える。
我々のアルゴリズムは河原林とThorupとは大きく異なり、Kargerの伐採フレームワーク(J.~ACM'00)に基づいている。
本アルゴリズムの応用について述べる。
i) このアルゴリズムは, グラフ内の近傍最小カットの集合のポリゴン表現を構築するための, より効率的なアルゴリズムに向かって進行する。
これは、最初に Bencz\'ur (FOCS'95) によって記述されたサボテン表現の一般化である。
(II) 隣接リストモデルにおける最小カットに対する最近の量子アルゴリズムの時間複雑性を$\widetilde O(n^{3/2})$から$\widetilde O(\sqrt{mn})$へ改善する。
(iii)複雑さ$O(m + n \log^6n)$の単純なグラフで最小カットを行う新しい種類のランダム化アルゴリズムを記述する。
わずかに密度の高いグラフの場合、これはランダムな収縮に基づく異なるアプローチを用いる現在の最良の$o(m + n \log^2 n)$アルゴリズムの複雑さと一致する。
私たちの仕事の重要な技術的貢献は次のとおりです。
m$ エッジとスパンディングツリー $t$ の重み付きグラフ $g$ を考えると、ノードが$t$ のエッジであるグラフ $h$ と、$h$ iff の2つのノード間にエッジがある場合、対応する 2 つの参照カット $t$ は、非自明な近似最小カット$g$ である。
我々は、$O(m \log^4 n)$の時間決定アルゴリズムを与え、$H$の森林を計算する。
関連論文リスト
- Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
我々は[Makarychev, Makarychev and Vijayaraghavan, STOC'12] の半ランダムグラフモデルを考える。
時間アルゴリズムは、カットされた$(A, B)$がサイズ$Omega(alpha)$である限り、alphad Cutの問題を最大$O(alpha)$ [MMV'12]に近似することが知られている。
この問題の微細な複雑さについて検討し,[MMV'12]と同じような性能を示す最初のニア線形時間サブルーチンを提示する。
論文 参考訳（メタデータ） (2024-06-07T11:40:54Z) - 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) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。
この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文 参考訳（メタデータ） (2021-10-29T07:35:46Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - 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) - Quantum complexity of minimum cut [0.2538209532048867]
隣接行列モデルにおける最小カット問題の量子クエリと時間複雑性を特徴付ける。
我々のアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。
論文 参考訳（メタデータ） (2020-11-19T13:51:49Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳（メタデータ） (2020-10-13T17:26:09Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。