論文の概要: Local Search on Vertex Coloring for Bipartite Graphs
- arxiv url: http://arxiv.org/abs/2606.09509v1
- Date: Mon, 08 Jun 2026 14:02:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-09 14:42:07.170431
- Title: Local Search on Vertex Coloring for Bipartite Graphs
- Title（参考訳）: 両部グラフの頂点色に関する局所探索
- Authors: Johanna Gasse,
- Abstract要約: 本研究では,局所的な最適解を求めるグラフ上での局所探索機能について検討する。
グレーボックスの局所的な検索突然変異演算子を導入し、より頻度の低い色を高い確率で除去する。
これは、ブラックボックスのランダムローカルサーチの指数的なチューン時間を大幅に改善する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Local search is a well-known heuristic method used in optimization. In this thesis, we explore its capabilities on the vertex coloring problem, an $NP$-hard problem with relevance in both theoretical analysis and practical application. To recognize limitations in the applicability of local search of the vertex coloring problem, we analyze local search landscapes on differently-structured bipartite graphs. We identify structures that ensure only global optima can exist as well as ones that enable the existence of non-global local optima, showing that on general bipartite graphs, it is possible for local search to return arbitrarily bad results. Further, we analyze the capabilities of local search on graphs where a local optimum can be found. To do so, we introduce a gray-box local search mutation operator that removes less frequent colors with higher probability and prove that it finds an optimal coloring on complete bipartite graphs in an expected run time of $Θ(n \log n)$. This is a drastic improvement to the exponential tun time of the black-box Random Local Search, showing that gray-box mutation operators can improve the run time of local search.
- Abstract（参考訳）: 局所探索は最適化においてよく知られたヒューリスティック手法である。
本論では,理論解析と実用的応用の両方に関連性のある$NP$-hard問題である頂点彩色問題におけるその機能について検討する。
頂点彩色問題に対する局所探索の適用性の限界を認識するため,異なる構造を持つ二部グラフ上の局所探索環境を解析した。
グローバルな最適性のみを保証できる構造と、非グローバルな局所最適性の存在を可能にする構造を同定し、一般的な二部グラフ上では、局所探索が任意に悪い結果を返すことができることを示す。
さらに、局所的な最適値が見つかるグラフ上での局所探索の能力を解析する。
そのため、グレーボックスの局所探索突然変異演算子を導入し、より高い確率で頻度の低い色を除去し、完全な二部グラフ上での最適な色付けを、期待実行時間$(n \log n)$で証明する。
これは、ブラックボックスのランダムローカルサーチの指数的なチューン時間を大幅に改善し、グレーボックスの突然変異演算子がローカルサーチの実行時間を改善することを示した。
関連論文リスト
- Faster 3D Gaussian Splatting Convergence via Structure-Aware Densification [52.517763621139956]
3Dガウススプラッティングは、リアルタイムのノベルビュー合成のための強力なシーン表現として登場した。
標準適応密度制御は画面空間の位置勾配に依存する。
本稿では,3次元ガウススプラッティングのための構造認識型密度化フレームワークを提案する。
論文 参考訳（メタデータ） (2026-04-30T15:37:20Z) - Neural Algorithmic Reasoning for Approximate $k$-Coloring with Recursive Warm Starts [5.645823801022895]
ノードカラー化におけるグラフニューラルネットワーク(GNN)の利用について検討する。
我々は,軽量なグリーディ局所探索アルゴリズムを導入し,暖かいスタートに使用するために$(k-1)-coloringを使用することで,それを改善することを示す。
数値実験により、局所探索アルゴリズムは小さな入力に対して優れているが、GNN$はスケールにおいて優れた性能を示すことが示された。
論文 参考訳（メタデータ） (2026-01-08T17:28:09Z) - Noise to the Rescue: Escaping Local Minima in Neurosymbolic Local Search [50.24983453990065]
結合と解離を min と max で表す Godel 論理に BP を適用することは SAT 問題解決のための局所探索アルゴリズムと等価であることを示す。
本稿では,モデルのロジットに雑音を付加し,局所最適化から逃れるゴデルトリックを提案する。
論文 参考訳（メタデータ） (2025-03-03T18:42:13Z) - Optimisation via encodings: a renormalisation group perspective [0.0]
最適化問題の解法として被覆符号化マップをどのように利用できるかを示す。
カバーエンコーディングマップに係わる粗粒化は、再正規化グループスキームで遭遇した粗粒化と強く類似していることが示される。
論文 参考訳（メタデータ） (2023-03-28T19:07:33Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - Time Complexity Analysis of Randomized Search Heuristics for the Dynamic
Graph Coloring Problem [15.45783225341009]
エッジを現在のグラフに追加する動的設定について検討する。
次に、ランダム化された検索の予測時間を分析し、高品質な解を再計算する。
論文 参考訳（メタデータ） (2021-05-26T13:00:31Z) - Deterministic spatial search using alternating quantum walks [0.0]
最適な量子ウォーク時間と頂点位相シフトの組に対して、構造化空間探索のための決定論的アルゴリズムが確立されていることを証明した。
これにより、同じグラフのクラスにおける元の空間探索アルゴリズムを改善し、50%の確率しか増幅できないことを示す。
この新たなフレームワークは、グラフ構造の他のファミリーに対する決定論的空間探索に容易に拡張できると期待されている。
論文 参考訳（メタデータ） (2021-04-08T14:32:48Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - Non-Local Graph Neural Networks [60.28057802327858]
本稿では,GNNに対する効果的な注意誘導ソート機能を備えた,シンプルで効果的な非局所集約フレームワークを提案する。
異種グラフデータセットを分析し,非局所的なGNNを評価するための徹底的な実験を行った。
論文 参考訳（メタデータ） (2020-05-29T14:50:27Z) - More Effective Randomized Search Heuristics for Graph Coloring Through
Dynamic Optimization [15.45783225341009]
進化的アルゴリズムは、動的最適化を用いて、二部グラフのグラフ彩色問題をより効率的に解くことができることを示す。
3つの島を用いた島式は、すべての$m$-edge二部グラフ上で$Theta(m)$の最適時間で成功し、子孫より優れている。
論文 参考訳（メタデータ） (2020-05-28T07:55:12Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。