論文の概要: The Packing Chromatic Number of the Infinite Square Grid is 15
- arxiv url: http://arxiv.org/abs/2301.09757v1
- Date: Mon, 23 Jan 2023 23:27:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2023-01-25 14:37:37.894776
- Title: The Packing Chromatic Number of the Infinite Square Grid is 15
- Title（参考訳）: 無限正方格子の包装色数は15である
- Authors: Bernardo Subercaseaux and Marijn J. H. Heule
- Abstract要約: Packing $k$-coloringは、グラフの標準概念である$k$-coloringのバリエーションである。
約2桁のオーダーで最もよく知られた方法を改善することにより、無限正方格子のパッキング数を証明した。
- 参考スコア（独自算出の注目度）: 5.863264019032882
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A packing $k$-coloring is a natural variation on the standard notion of graph
$k$-coloring, where vertices are assigned numbers from $\{1, \ldots, k\}$, and
any two vertices assigned a common color $c \in \{1, \ldots, k\}$ need to be at
a distance greater than $c$ (as opposed to $1$, in standard graph colorings).
Despite a sequence of incremental work, determining the packing chromatic
number of the infinite square grid has remained an open problem since its
introduction in 2002. We culminate the search by proving this number to be 15.
We achieve this result by improving the best-known method for this problem by
roughly two orders of magnitude. The most important technique to boost
performance is a novel, surprisingly effective propositional encoding for
packing colorings. Additionally, we developed an alternative symmetry-breaking
method. Since both new techniques are more complex than existing techniques for
this problem, a verified approach is required to trust them. We include both
techniques in a proof of unsatisfiability, reducing the trusted core to the
correctness of the direct encoding.
- Abstract（参考訳）: ここで、頂点は$\{1, \ldots, k\}$ から割り当てられ、共通色に割り当てられたすべての2つの頂点は$c \in \{1, \ldots, k\}$ 以上の距離でなければならない(標準的なグラフ彩色では$$$ である)。
漸進的な研究の連続にもかかわらず、無限平方格子の包装色数を決定することは2002年の導入以来未解決の問題のままである。
我々はこの数字を15と証明することで探索を成す。
我々は,この問題に対する最もよく知られた手法をおよそ2桁改善することで,この結果を得る。
パフォーマンスを向上する最も重要なテクニックは、パッキングカラー化のための新しい、驚くほど効果的な命題エンコーディングである。
さらに,代替対称性破砕法を開発した。
どちらの新しいテクニックも既存のテクニックよりも複雑であるため、信頼するには検証されたアプローチが必要である。
両手法を不満足の証明に含め、信頼されたコアを直接符号化の正しさに還元する。
関連論文リスト
- Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges [8.499685241219366]
我々は、エッジカラーのハイパーグラフをクラスタリングするためのフレームワークを検討し、そこでは、彼らが参加する主要なマルチウェイインタラクションのタイプに基づいてオブジェクトをクラスタリングすることを目的としている。
よく研究されている1つの目的は、満足できないハイパーエッジの数を最小限に抑えるためにノードを色付けすることである。
最適性は同じだが、近似するよりもはるかに難しい、満足度の高いエッジを最大化する新しいアルゴリズムを提供する。
論文 参考訳（メタデータ） (2025-02-18T16:20:50Z) - A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。
この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
論文 参考訳（メタデータ） (2024-06-26T18:19:10Z) - Edge coloring lattice graphs [0.0]
格子グラフのパッチの適切なエッジ色付けに必要な条件を翻訳により証明する。
この条件は、無限格子グラフの極小または極小の辺色付けを見つける方法の基礎となる。
我々の研究は、量子シミュレーション、量子最適化、量子状態検証といった分野において、最小深度量子回路を提供することによって、直接的な応用を見出した。
論文 参考訳（メタデータ） (2024-02-13T19:38:58Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Withdrawn: A Measurement-based Algorithm for Graph Colouring [0.5482532589225553]
この文書の以前のバージョンでは、記述されたアルゴリズムの一部のランタイムを誤って解釈した。
グラフが存在すれば$d$カラーの適切な色付けを見つけるための新しいアルゴリズム的アプローチを提案する。
論文 参考訳（メタデータ） (2021-11-29T09:17:34Z) - Evolutionary Algorithm for Graph Coloring Problem [0.0]
グラフ色問題(GCP)は、コンピュータ科学において最も研究されているNP-HARD問題の一つである。
本稿では、色数の理論上界、すなわち最大外度+1から始める。
進化の過程で、いくつかの色は、世代ごとに動的に色の数を減らすために使われない。
論文 参考訳（メタデータ） (2021-11-17T12:16:57Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
グラフカラー化のための"古典的"メタヒューリスティックス(classical metaheuristics)の最高のツールと、ディープニューラルネットワークを組み合わせた新しいフレームワークを提案する。
アルゴリズムにおけるディープラーニングの寄与についての研究は、この問題に対するより良い解を得るのに有用な関連パターンを学習することが可能であることを強調している。
論文 参考訳（メタデータ） (2021-09-13T13:17:41Z) - Optimizing Ansatz Design in QAOA for Max-cut [0.9126120966154119]
CNOTは現代の量子コンピュータの主要なエラー源の1つである。
本稿では,回路内のCNOTゲート数を削減するための2つのハードウェア独立手法を提案する。
論文 参考訳（メタデータ） (2021-06-05T06:43:48Z) - GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
我々は,最も困難なブラックボックス設定の1つにおいて,逆例を生成するためのフレームワークを提案する。
我々のフレームワークは、ディープネットワークの決定境界は通常、データサンプルの近傍で小さな平均曲率を持つという観察に基づいている。
論文 参考訳（メタデータ） (2020-03-13T20:03:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。