論文の概要: Unfolding Boxes with Local Constraints

• arxiv url: http://arxiv.org/abs/2506.01079v1
• Date: Sun, 01 Jun 2025 16:30:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:33.921456
• Title: Unfolding Boxes with Local Constraints
• Title（参考訳）: 局所制約付き折り畳み箱
• Authors: Long Qian, Eric Wang, Bernardo Subercaseaux, Marijn J. H. Heule,
• Abstract要約: 既存のSATエンコーディングは、グローバルな制約の存在によって妨げられていると我々は主張する。 我々はこれらのグローバル制約を単純なローカル制約で置き換える新しいSATベースのアプローチを提案する。
• 参考スコア（独自算出の注目度）: 8.784862212364697
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of finding and enumerating polyominos that can be folded into multiple non-isomorphic boxes. While several computational approaches have been proposed, including SAT, randomized algorithms, and decision diagrams, none has been able to perform at scale. We argue that existing SAT encodings are hindered by the presence of global constraints (e.g., graph connectivity or acyclicity), which are generally hard to encode effectively and hard for solvers to reason about. In this work, we propose a new SAT-based approach that replaces these global constraints with simple local constraints that have substantially better propagation properties. Our approach dramatically improves the scalability of both computing and enumerating common box unfoldings: (i) while previous approaches could only find common unfoldings of two boxes up to area 88, ours easily scales beyond 150, and (ii) while previous approaches were only able to enumerate common unfoldings up to area 30, ours scales up to 60. This allows us to rule out 46, 54, and 58 as the smallest areas allowing a common unfolding of three boxes, thereby refuting a conjecture of Xu et al. (2017).
• Abstract（参考訳）: 複数の非同型ボックスに折り畳むことができるポリオミノの発見と列挙の問題を考える。 SAT、ランダム化アルゴリズム、決定図など、いくつかの計算手法が提案されているが、大規模に実行することはできない。 既存のSATエンコーディングはグローバルな制約(例えば、グラフ接続性や非循環性)の存在によって妨げられていると我々は主張する。 本研究では、これらのグローバル制約を、より優れた伝搬特性を持つ単純な局所制約に置き換える新しいSATベースのアプローチを提案する。 私たちのアプローチは、コンピューティングのスケーラビリティを劇的に改善し、共通ボックスの展開を列挙します。 (i) 従来のアプローチでは、2箱の共通展開が88までしか見つからなかったが、我々の展開は150を超えると容易にスケールできる。 (II) 従来の手法では, 共通展開を30領域まで列挙するしかなかったが, 我々の手法は60領域までスケールする。 これにより、46, 54, 58 を3つの箱の共通展開を可能にする最小の領域として定義することができ、Xu et al (2017) の予想を否定することができる。

関連論文リスト

• Generalized Schrödinger Bridge Matching [54.171931505066]
  一般化Schr"odinger Bridge (GSB) 問題設定は、機械学習の内外を問わず、多くの科学領域で一般的である。 我々は最近の進歩に触発された新しいマッチングアルゴリズムである一般化シュリンガーブリッジマッチング(GSBM)を提案する。 このような一般化は条件最適制御の解法として、変分近似を用いることができることを示す。
  論文  参考訳（メタデータ） (2023-10-03T17:42:11Z)
• Mutually unbiased bases as a commuting polynomial optimisation problem [0.0]
  我々は、実数に対する最適化問題として、相互に偏りのない基底の問題を考察する。 最適化手法を多数組み合わせた2つの手法を用いる。 このようなアルゴリズムが最終的に有限メモリで次元6に関するオープンな問題を解くことを実証する。
  論文  参考訳（メタデータ） (2023-08-03T17:14:22Z)
• A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP [0.0]
  本稿では,多次元スケーリングを用いて,まず非ユークリッド空間からユークリッド空間へ点を投影し,そのアルゴリズムを初期化する凸包を生成する。 提案アルゴリズムを評価するために、TSPLIBデータセットにセパレータを追加するか、L1ノルムを計量として使用することにより、非ユークリッド空間を生成する。
  論文  参考訳（メタデータ） (2023-02-05T13:56:19Z)
• ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set [48.57120672468062]
  本稿では、2つの革新的な手法を取り入れたMIS問題に対する効率的なアルゴリズムを提案する。 提案アルゴリズムは、解の質、計算効率、安定性の点で最先端のアルゴリズムより優れている。
  論文  参考訳（メタデータ） (2022-08-16T14:39:38Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• 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)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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