論文の概要: Simple vertex coloring algorithms
- arxiv url: http://arxiv.org/abs/2102.07089v1
- Date: Sun, 14 Feb 2021 07:27:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-11 04:26:56.035156
- Title: Simple vertex coloring algorithms
- Title（参考訳）: 単純頂点カラー化アルゴリズム
- Authors: Jackson Morris and Fang Song
- Abstract要約: 1 + epsilon)Delta$-coloring に対して簡単なアルゴリズムを与える。
これは$tildeO(epsilon-1n4/3)$クエリを生成する量子クエリアルゴリズムに適応することができる。
- 参考スコア（独自算出の注目度）: 2.8808678188754637
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a graph $G$ with $n$ vertices and maximum degree $\Delta$, it is known
that $G$ admits a vertex coloring with $\Delta + 1$ colors such that no edge of
$G$ is monochromatic. This can be seen constructively by a simple greedy
algorithm, which runs in time $O(n\Delta)$.
Very recently, a sequence of results (e.g., [Assadi et. al. SODA'19, Bera et.
al. ICALP'20, Alon Assadi Approx/Random'20]) show randomized algorithms for
$(\epsilon + 1)\Delta$-coloring in the query model making
$\tilde{O}(n\sqrt{n})$ queries, improving over the greedy strategy on dense
graphs. In addition, a lower bound of $\Omega(n\sqrt n)$ for any
$O(\Delta)$-coloring is established on general graphs.
In this work, we give a simple algorithm for $(1 + \epsilon)\Delta$-coloring.
This algorithm makes $O(\epsilon^{-1/2}n\sqrt{n})$ queries, which matches the
best existing algorithms as well as the classical lower bound for sufficiently
large $\epsilon$. Additionally, it can be readily adapted to a quantum query
algorithm making $\tilde{O}(\epsilon^{-1}n^{4/3})$ queries, bypassing the
classical lower bound. Complementary to these algorithmic results, we show a
quantum lower bound of $\Omega(n)$ for $O(\Delta)$-coloring.
- Abstract（参考訳）: グラフ$G$と$n$頂点と最大次数$\Delta$が与えられたとき、$G$は$\Delta + 1$カラーの頂点色を認め、$G$の辺が単色でないことが知られている。
これは、時間$O(n\Delta)$で実行される単純なgreedyアルゴリズムによって構成的に見ることができる。
ごく最近、一連の結果(例:assadi et. al. soda'19, bera et. al. icalp'20, alon assadi approx/random'20])がクエリモデルで$(\epsilon + 1)\delta$-coloringのランダム化アルゴリズムを示し、$\tilde{o}(n\sqrt{n})$クエリを作成し、密グラフの欲望戦略を改善した。
さらに、任意の$O(\Delta)$-色付けに対して$\Omega(n\sqrt n)$の低い境界が一般グラフ上で成立する。
この研究では、$(1 + \epsilon)\delta$-coloringの単純なアルゴリズムを与える。
このアルゴリズムは$O(\epsilon^{-1/2}n\sqrt{n})$クエリを生成する。
さらに、量子クエリアルゴリズムに容易に適用でき、古典的な下限をバイパスして$\tilde{o}(\epsilon^{-1}n^{4/3})$クエリを作成することができる。
これらのアルゴリズムの結果を補完し、$O(\Delta)$-coloringに対して$Omega(n)$の量子下界を示す。
関連論文リスト
- A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。
特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-28T21:23:40Z) - A faster and simpler algorithm for learning shallow networks [10.595936992218856]
ラベル付き例から、$k$ReLUアクティベーションの線形結合を学習する、よく研究された問題を再考する。
ここでは、アルゴリズムのよりシンプルなワンステージバージョンが十分であることを示し、そのランタイムは、わずか$(d/varepsilon)O(k2)$である。
論文 参考訳（メタデータ） (2023-07-24T03:04:10Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - 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) - 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) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。