論文の概要: A Parallel Approach to Counting Exact Covers Based on Decomposability Property

• arxiv url: http://arxiv.org/abs/2604.14627v1
• Date: Thu, 16 Apr 2026 05:13:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-17 21:29:31.7338
• Title: A Parallel Approach to Counting Exact Covers Based on Decomposability Property
• Title（参考訳）: 分解性特性に基づく厳密被覆の並列計算法
• Abstract要約: 正確なカバー問題は、AIの領域で広く応用される古典的なNPハード問題である。 決定分解可能な正規形式(略してZDNNF)のゼロ抑圧変種を提案する。 DXDと呼ばれる新しい並列アルゴリズムを設計し、全完全被覆の集合を表す決定-ZDNNFを構築する。
• 参考スコア（独自算出の注目度）: 14.88250567379226
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The exact cover problem is a classical NP-hard problem with broad applications in the area of AI. Algorithm DXZ is a method to count exact covers representing by zero-suppressed binary decision diagrams (ZBDDs). In this paper, we propose a zero-suppressed variant of decision decomposable negation normal form (in short, decision-ZDNNF), which is strictly more succinct than ZBDDs. We then design a novel parallel algorithm, namely DXD, which constructs a decision-ZDNNF representing the set of all exact covers. Furthermore, we improve DXD by dynamically updating connected components. The experimental results demonstrate that the improved DXD algorithm outperforms all of state-of-the-art methods.
• Abstract（参考訳）: 正確なカバー問題は、AIの領域で広く応用される古典的なNPハード問題である。 アルゴリズムDXZはゼロ抑圧二分決定図(ZBDD)で表される正確な被覆を数える手法である。 本稿では、ZBDDよりも厳密な決定分解型否定正規形(略してZDNNF)のゼロ抑圧型変種を提案する。 DXDと呼ばれる新しい並列アルゴリズムを設計し、全完全被覆の集合を表す決定-ZDNNFを構築する。 さらに、接続されたコンポーネントを動的に更新することでDXDを改善する。 実験の結果,改良されたDXDアルゴリズムは最先端の手法よりも優れていた。

関連論文リスト

• Block Decomposable Methods for Large-Scale Optimization Problems [0.0]
  この論文は、方向乗算器(ADMM)とブロック座標降下法(BCD)に焦点を当てている。 新たなアルゴリズムを導入し,問題を解くための2つの方法を提案する。
  論文  参考訳（メタデータ） (2026-01-13T22:18:57Z)
• Direct Diffusion Bridge using Data Consistency for Inverse Problems [65.04689839117692]
  拡散モデルに基づく逆問題解法は優れた性能を示したが、速度は制限されている。 いくつかの最近の研究は、拡散プロセスを構築し、クリーンで破損したものを直接ブリッジすることでこの問題を緩和しようと試みている。 微調整を必要とせずにデータの一貫性を強制する改良された推論手順を提案する。
  論文  参考訳（メタデータ） (2023-05-31T12:51:10Z)
• Modular Differential Evolution [0.0]
  本稿では,一般的な微分進化(DE)アルゴリズムのためのモジュラーフレームワークを提案する。 モジュールDEの設定のチューニングは、我々のフレームワークで再現された一般的なDEバージョンのセットよりも大幅に優れています。
  論文  参考訳（メタデータ） (2023-04-19T09:29:48Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
  本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。 鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。 このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
  論文  参考訳（メタデータ） (2022-11-22T10:18:33Z)
• Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem [18.19836641663039]
  我々は,0-1 MKPを解くために,進化計算と正確なアルゴリズムを組み合わせた新しいアルゴリズムを提案する。 一連のソリューションを維持し、人口の情報を利用して、優れた部分的な割り当てを抽出する。 既存のアルゴリズムよりも優れた解を見つけ、大規模で難しい10のインスタンスに新しい下位境界を提供する。
  論文  参考訳（メタデータ） (2022-10-08T05:11:47Z)
• Self-adjusting optimization algorithm for solving the setunion knapsack problem [0.3128201162068913]
  set-union knapsack problem (SUKP) は制約付き合成最適化問題である。 アイテムと要素の観点からSUKPを近似する2つの自己調整最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-01-23T14:15:49Z)
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization [111.24899593052851]
  条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。 ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。 1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
  論文  参考訳（メタデータ） (2021-09-18T07:08:11Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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