Fugu-MT 論文翻訳(概要): Advanced Tools and Methods for Treewidth-Based Problem Solving -- Extended Abstract

論文の概要: Advanced Tools and Methods for Treewidth-Based Problem Solving -- Extended Abstract

arxiv url: http://arxiv.org/abs/2208.11340v1
Date: Wed, 24 Aug 2022 07:43:58 GMT
ステータス: 処理完了
システム内更新日: 2022-08-25 13:21:56.612242
Title: Advanced Tools and Methods for Treewidth-Based Problem Solving -- Extended Abstract
Title（参考訳）: treewidthベースの問題解決のための高度なツールと手法 -extended abstract
Authors: Markus Hecher
Abstract要約: この研究は、論理ベースの問題とツリー幅ベースの方法とそれを解決するツールに焦点を当てている。本稿では,分解誘導(DG)による新しいタイプの問題削減について述べる。木幅を直接利用して,Satの拡張を効率的に解くアルゴリズムを実装した。
参考スコア（独自算出の注目度）: 9.480212602202517
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Computer programs, so-called solvers, for solving the well-known Boolean satisfiability problem (Sat) have been improving for decades. Among the reasons, why these solvers are so fast, is the implicit usage of the formula's structural properties during solving. One of such structural indicators is the so-called treewidth, which tries to measure how close a formula instance is to being easy (tree-like). This work focuses on logic-based problems and treewidth-based methods and tools for solving them. Many of these problems are also relevant for knowledge representation and reasoning (KR) as well as artificial intelligence (AI) in general. We present a new type of problem reduction, which is referred to by decomposition-guided (DG). This reduction type forms the basis to solve a problem for quantified Boolean formulas (QBFs) of bounded treewidth that has been open since 2004. The solution of this problem then gives rise to a new methodology for proving precise lower bounds for a range of further formalisms in logic, KR, and AI. Despite the established lower bounds, we implement an algorithm for solving extensions of Sat efficiently, by directly using treewidth. Our implementation is based on finding abstractions of instances, which are then incrementally refined in the process. Thereby, our observations confirm that treewidth is an important measure that should be considered in the design of modern solvers.
Abstract（参考訳）: よく知られたブール適合性問題(Sat)を解決するためのコンピュータプログラムは、数十年にわたって改善されてきた。これらの解法が高速である理由は、解法中の公式の構造的性質を暗黙的に用いているからである。そのような構造的指標の1つは、いわゆるtreewidthであり、式インスタンスが(ツリーのような)容易さにどれだけ近いかを測定する。この研究は、論理ベースの問題とツリー幅ベースの方法とそれを解決するツールに焦点を当てている。これらの問題の多くは、知識表現と推論(KR)、一般の人工知能(AI)にも関係している。本稿では,分解誘導(DG)と呼ばれる新しいタイプの問題削減について述べる。この還元型は2004年以来開いている有界木幅の量子化ブール公式(qbfs)の問題を解決する基礎となっている。この問題の解決策は、論理学、KR、AIのさらなる形式主義の分野において、正確な下限を証明する新しい方法論を生み出した。確立された下限にもかかわらず,treewidth を用いて sat の拡張を効率的に解くアルゴリズムを実装した。私たちの実装は、インスタンスの抽象化を見つけることに基づいています。したがって,木幅は現代の解法の設計において考慮すべき重要な指標であることを確認した。

関連論文リスト

Solving Projected Model Counting by Utilizing Treewidth and its Limits [23.81311815698799]
予測モデルカウント(PMC)を解く新しいアルゴリズムを提案する。いわゆる「ツリー幅」が最も顕著な構造パラメータの1つであるという観測から着想を得て,本アルゴリズムは入力インスタンスの一次グラフの小さなツリー幅を利用する。
論文参考訳（メタデータ） (2023-05-30T17:02:07Z)
FastDiagP: An Algorithm for Parallelized Direct Diagnosis [64.65251961564606]
FastDiagは、競合を事前に決定せずに診断計算をサポートする典型的な直接診断アルゴリズムである。本稿では,投機的プログラミングのアイデアに基づく新しいアルゴリズムであるFastDiagPを提案する。このメカニズムは、高速な回答で一貫性チェックを提供し、アルゴリズムのランタイムパフォーマンスを高めるのに役立つ。
論文参考訳（メタデータ） (2023-05-11T16:26:23Z)
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)
Efficient Knowledge Compilation Beyond Weighted Model Counting [7.828647825246474]
このような問題に対する一般的なフレームワークとして,第2レベル代数モデルカウント (2AMC) を導入している。 KC(Knowledge Compilation)に基づく第1レベルのテクニックは、変数順序制約を課すことで、特定の2AMCインスタンスに適応している。 2AMC問題の論理構造を利用して、これらの制約の一部を省略し、負の効果を制限できることが示される。
論文参考訳（メタデータ） (2022-05-16T08:10:40Z)
What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization [8.879790406465556]
本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
論文参考訳（メタデータ） (2022-01-25T17:37:34Z)
Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
論文参考訳（メタデータ） (2021-04-14T09:22:42Z)
Accelerating Recursive Partition-Based Causal Structure Learning [4.357523892518871]
帰納的因果探索アルゴリズムは、より小さなサブプロブレムで条件独立性テスト(CI)を用いて良い結果をもたらす。本稿では,少数のCIテストと望ましくない関係を特定できる汎用因果構造改善戦略を提案する。次に,合成および実データ集合における解の質と完了時間の観点から,最先端アルゴリズムに対する性能を実証的に評価する。
論文参考訳（メタデータ） (2021-02-23T08:28:55Z)
Learning by Fixing: Solving Math Word Problems with Weak Supervision [70.62896781438694]
数学用語問題(mwps)の従来のニューラルネットワークソルバは、完全な監視によって学習され、多様なソリューションを生み出すことができない。 MWPを学習するためのテキスト弱教師付きパラダイムを提案する。この手法は最終回答のアノテーションのみを必要とし、単一の問題に対して様々な解決策を生成できる。
論文参考訳（メタデータ） (2020-12-19T03:10:21Z)
From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文参考訳（メタデータ） (2020-06-05T10:56:52Z)
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)

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

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