論文の概要: 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桁改善することで,この結果を得る。 パフォーマンスを向上する最も重要なテクニックは、パッキングカラー化のための新しい、驚くほど効果的な命題エンコーディングである。 さらに,代替対称性破砕法を開発した。 どちらの新しいテクニックも既存のテクニックよりも複雑であるため、信頼するには検証されたアプローチが必要である。 両手法を不満足の証明に含め、信頼されたコアを直接符号化の正しさに還元する。

関連論文リスト

• 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)
• Kernelized multi-graph matching [0.0]
  本稿では,グラフの属性とエッジの両方を扱う,新しいカーネル化されたマルチグラフマッチング手法を提案する。 結果の安定性の向上につながるプロジェクタをいくつか提案する。
  論文  参考訳（メタデータ） (2022-10-11T07:22:47Z)
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race [4.416484585765029]
  Weisfeiler-Lemanアルゴリズムは、グラフ学習には基本的であり、グラフカーネルやグラフニューラルネットワークの成功には中心となる。 本研究では, 着色速度を緩やかに収束させることができる, 漸進的な地区改良のための枠組みを提案する。 提案手法は,既存のグラフカーネルの新しい変種を導出し,最適割り当てによるグラフ編集距離を近似するために用いられる。
  論文  参考訳（メタデータ） (2022-09-19T14:37:35Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• Fast Gradient Non-sign Methods [67.56549792690706]
  Fast Gradient Non-sign Method (FGNM) は一般的なルーチンであり、グラデーションベースの攻撃において従来の$sign$操作をシームレスに置き換えることができる。 我々の手法は、textbf27.5% と textbf9.5% でそれらを上回ります。
  論文  参考訳（メタデータ） (2021-10-25T08:46:00Z)
• 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)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization [6.037383467521294]
  我々は $ell_0$ 正規化回帰のための新しい正確な MIP フレームワークを提案する。 私たちのフレームワークは、$p sim 107$までスケールでき、少なくとも5,000$xのスピードアップを達成できます。 実装をツールキットL0BnBでオープンソースにしています。
  論文  参考訳（メタデータ） (2020-04-13T18:45:29Z)
• GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
  我々は,最も困難なブラックボックス設定の1つにおいて,逆例を生成するためのフレームワークを提案する。 我々のフレームワークは、ディープネットワークの決定境界は通常、データサンプルの近傍で小さな平均曲率を持つという観察に基づいている。
  論文  参考訳（メタデータ） (2020-03-13T20:03:01Z)
• Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning [7.6146285961466]
  我々は、すべての$gamma 1$に対して一様に束縛されたサンプル複雑性を持つ新しいアルゴリズムのクラスを導入する。 最適化されたステップサイズシーケンスとQ-ラーニングアルゴリズムの共分散は、1/(1-ガンマ)$の二次関数であることを示す。
  論文  参考訳（メタデータ） (2020-02-24T15:12:41Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。