Fugu-MT 論文翻訳(概要): A Grover search-based algorithm for the list coloring problem

論文の概要: A Grover search-based algorithm for the list coloring problem

arxiv url: http://arxiv.org/abs/2108.09061v2
Date: Thu, 3 Mar 2022 13:38:04 GMT
ステータス: 処理完了
システム内更新日: 2023-03-17 23:11:56.926240
Title: A Grover search-based algorithm for the list coloring problem
Title（参考訳）: 一覧色問題に対するグロバー探索に基づくアルゴリズム
Authors: Sayan Mukherjee
Abstract要約: 本稿では,Grover 探索に基づく量子アルゴリズムを提案する。我々のアルゴリズムは、制限された特定のケースでは古典的な場合に比べて複雑性が低いが、自然に考慮されたリストやグラフが任意である場合の徹底的な探索を改善する。
参考スコア（独自算出の注目度）: 1.332560004325655
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Graph coloring is a computationally difficult problem, and currently the best known classical algorithm for $k$-coloring of graphs on $n$ vertices has runtimes $\Omega(2^n)$ for $k\ge 5$. The list coloring problem asks the following more general question: given a list of available colors for each vertex in a graph, does it admit a proper coloring? We propose a quantum algorithm based on Grover search to quadratically speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases where the lists and graphs considered are arbitrary in nature.
Abstract（参考訳）: グラフ彩色は計算的に難しい問題であり、現在、$n$ vertices 上のグラフの $k$-coloring のための最もよく知られている古典的アルゴリズムはランタイム $\Omega(2^n)$ for $k\ge 5$ である。グラフの各頂点について利用可能な色のリストが与えられた場合、適切な色付けは認められるか? 本稿では,2次探索を高速化するグローバー探索に基づく量子アルゴリズムを提案する。我々のアルゴリズムは、制限された特定のケースでは古典的な場合に比べて複雑性が低いが、本質的にはリストやグラフが任意である場合の徹底的な探索を改善する。

関連論文リスト

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)
Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文参考訳（メタデータ） (2023-06-29T14:57:56Z)
Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文参考訳（メタデータ） (2022-10-04T04:36:15Z)
Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文参考訳（メタデータ） (2022-07-04T19:33:06Z)
Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文参考訳（メタデータ） (2022-01-25T00:10:03Z)
Withdrawn: A Measurement-based Algorithm for Graph Colouring [0.5482532589225553]
この文書の以前のバージョンでは、記述されたアルゴリズムの一部のランタイムを誤って解釈した。グラフが存在すれば$d$カラーの適切な色付けを見つけるための新しいアルゴリズム的アプローチを提案する。
論文参考訳（メタデータ） (2021-11-29T09:17:34Z)
A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
グラフカラー化のための"古典的"メタヒューリスティックス(classical metaheuristics)の最高のツールと、ディープニューラルネットワークを組み合わせた新しいフレームワークを提案する。アルゴリズムにおけるディープラーニングの寄与についての研究は、この問題に対するより良い解を得るのに有用な関連パターンを学習することが可能であることを強調している。
論文参考訳（メタデータ） (2021-09-13T13:17:41Z)
Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem [15.45783225341009]
エッジを現在のグラフに追加する動的設定について検討する。次に、ランダム化された検索の予測時間を分析し、高品質な解を再計算する。
論文参考訳（メタデータ） (2021-05-26T13:00:31Z)
Simple vertex coloring algorithms [2.8808678188754637]
1 + epsilon)Delta$-coloring に対して簡単なアルゴリズムを与える。これは$tildeO(epsilon-1n4/3)$クエリを生成する量子クエリアルゴリズムに適応することができる。
論文参考訳（メタデータ） (2021-02-14T07:27:10Z)
Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文参考訳（メタデータ） (2020-11-26T18:22:21Z)
A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs [0.0]
最大マッチングのための量子アルゴリズムを設計する。特に、$n$ノードと$m$エッジを持つグラフの場合、我々のアルゴリズムは行列モデルで$O(n7/4)クエリを生成する。
論文参考訳（メタデータ） (2020-10-05T20:34:39Z)

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