論文の概要: Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry

• arxiv url: http://arxiv.org/abs/2606.26399v1
• Date: Wed, 24 Jun 2026 21:34:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-26 18:46:32.087655
• Title: Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry
• Title（参考訳）: 組合せ幾何学における極端問題に対する幾何学的MCTS
• Authors: Luoning Zhang, Xu Zhuang, Tianhao Wang, Nathan Kaplan,
• Abstract要約: 幾何学において、n×n$グリッドの点の構成を問う極端問題について研究する。 提案手法は、実行可能なアクション空間への漸進的な更新を通じて、厳密な幾何学的制約を強制する。 検討した6つの問題のうちの5つに、新しい最もよく知られた計算結果を確立する。
• 参考スコア（独自算出の注目度）: 3.8362220332316626
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study certain extremal problems in combinatorial geometry that ask about configurations of points in an $n \times n$ grid that satisfy strict, global geometric constraints. Classical exact solvers suffer from combinatorial explosion for these types of problems, and standard reinforcement learning and transformer-based models struggle with the sparse reward "validity cliff" and quadratic token-consumption limits. To overcome these bottlenecks, we propose a Geometry-Aware Monte Carlo Tree Search (MCTS) framework. Our approach strictly enforces geometric constraints through incremental updates to the feasible action space. For constraints about collections of collinear points, like those that occur in the classic No-Three-in-Line problem (Max-N3IL), this mechanism reduces the constraint checking complexity from $O(n^3)$ to $O(n^2)$. To improve search efficiency, we exploit geometric symmetries in two ways: canonical pruning during node expansion to reduce the branching factor, and symmetric batch transitions to accelerate the discovery of promising configurations. We perform extensive experiments and establish new best-known computational results on five out of six of the problems that we considered. Notably, for Max-N3IL we find configurations of size roughly $1.8 n$ for grids of size $82 \le n \le 119$. For the Smallest Complete Set problem, we find configurations of size roughly $0.95 n$, providing new upper bounds within the tested grids. This work establishes Geometry-Aware MCTS as a highly adaptable framework for discovering novel configurations in combinatorial geometry.
• Abstract（参考訳）: 我々は、厳密で大域的な幾何学的制約を満たす$n \times n$ gridにおける点の設定を問う組合せ幾何学における極端問題について研究する。 古典的な厳密な解法はこれらの問題の組合せ的爆発に悩まされ、標準的な強化学習とトランスフォーマーベースのモデルは、まばらな報酬である「価値の崖」と二次的なトークン消費限界に苦しむ。 これらのボトルネックを克服するために,Geometry-Aware Monte Carlo Tree Search (MCTS) フレームワークを提案する。 提案手法は、実行可能なアクション空間への漸進的な更新を通じて、厳密な幾何学的制約を強制する。 古典的なNo-Three-in-Line問題(Max-N3IL)で発生するようなコリニア点の集合に関する制約に対して、このメカニズムは制約チェックの複雑さを$O(n^3)$から$O(n^2)$に還元する。 探索効率を向上させるために,ノード拡張時の正準プルーニングによる分岐係数の低減と,有望な構成の発見を促進する対称的バッチ遷移という2つの方法で幾何学的対称性を利用する。 これまでに検討した6つの問題のうち5つについて、広範囲な実験を行い、新しい最もよく知られた計算結果を確立する。 注目すべきは、Max-N3ILでは、サイズが約1.8n$で、サイズが82 \le n \le 119$であることだ。 最小完全集合問題に対しては、約0.95 n$のサイズの構成を見つけ、テストされたグリッド内に新しい上限を与える。 この研究は、組合せ幾何学における新しい構成を発見するための高度に適応可能なフレームワークとしてGeometry-Aware MCTSを確立する。

関連論文リスト

• Internalizing Geometric Law: Learning from Solver Residuals for Precision-Critical Generation [2.459492253868525]
  自然言語からのオープンエンド幾何合成について検討する。 私たちは、宣言的制約を微分可能な損失にコンパイルするプログラマブルな幾何学的DSLであるPyGeoXをリリースします。 本稿では,SAR(Saturating Additive Rewards)を提案する。
  論文  参考訳（メタデータ） (2026-06-08T09:44:31Z)
• Mesh Graph Neural Network Framework for Accelerating Finite Element Simulation for Arbitrary Geometries [0.126928839393823]
  この研究は、任意の穴形状を持つ2次元構造体におけるフォン・ミセスの応力場を予測するメッシュグラフネットワーク(MGN)を提案する。 絶対ノード座標を特徴とする従来の機械学習アプローチとは異なり、提案されたモデルは既存のMGNフレームワークに基づいて構築される。 従来のモデルでは$R2 approx 0.01$-$0.86$と対照的に、このモデルは目に見えない幾何と見えない負荷で$R2 geq 0.97$を達成する。
  論文  参考訳（メタデータ） (2026-06-06T18:17:08Z)
• Swap Regret Minimization Through Response-Based Approachability [66.39400409563976]
  オンライン最適化において,スワップ後悔という異なる概念を最小化することの問題点を考察する。 我々は、一般凸集合に対して$O(d3/2 sqrtT)$リニアスワップ後悔を保証し、集合が中央対称であるときに$O(d sqrtT)$を保証し、より単純で効率的なアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2026-02-05T23:43:25Z)
• An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
  量子ビット効率の最適化を幾何学的問題として再検討する。 局所一貫性問題は、Sherali-Adams level-2 polytope $mathrmSA(2)$とちょうど一致する。
  論文  参考訳（メタデータ） (2025-11-11T15:38:57Z)
• On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
  平面トーラスから構築したグラフ上での最大独立集合(MIS)問題として問題を再構成することにより、$m_1(mathbbR2)$を推定する新しいアプローチを導入する。 提案手法の理論的正当性によって支持された実験結果から, 十分に広い範囲のパラメータに対して, この手法が既知の下界を改善できないことを示す。
  論文  参考訳（メタデータ） (2024-11-20T12:07:19Z)
• Geometric Clifford Algebra Networks [53.456211342585824]
  本稿では,動的システムのモデリングのためのGeometric Clifford Algebra Networks (GCANs)を提案する。 GCANは幾何学的(クリフォード)代数を用いた対称性群変換に基づいている。
  論文  参考訳（メタデータ） (2023-02-13T18:48:33Z)
• NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems [0.0]
  我々は,グラフ上の一般的な最適化問題に対して,決定過程(MDP)を定義することによって,様々な木にまたがる問題を解く新しいフレームワークであるNeuroPrimを提案する。 この枠組みをユークリッド空間上の3つの難しい問題に適用する: Degree-constrained Minimum Spanning Tree (DCMST) 問題、最小コストスパンニングツリー (MRCST) 問題、ルーティンググラフ (STP) におけるスタイナーツリー問題。
  論文  参考訳（メタデータ） (2022-10-22T13:49:29Z)
• A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching [69.14632473279651]
  本稿では,3次元形状間の幾何学的一貫したマッピング空間をグローバルに最適化するスケーラブルなアルゴリズムを提案する。 従来の解法よりも数桁高速なラグランジュ双対問題と結合した新しい原始問題を提案する。
  論文  参考訳（メタデータ） (2022-04-27T09:47:47Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。 我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
  論文  参考訳（メタデータ） (2021-01-18T15:40:27Z)

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

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