論文の概要: Threshold Treewidth and Hypertree Width

• arxiv url: http://arxiv.org/abs/2210.07040v1
• Date: Thu, 13 Oct 2022 13:53:59 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-14 17:08:53.268863
• Title: Threshold Treewidth and Hypertree Width
• Title（参考訳）: Threshold Treewidth と Hypertree Width
• Authors: Andre Schidler, Robert Ganian, Manuel Sorge, Stefan Szeider
• Abstract要約: 樹木幅と高木幅は、制約満足度(CSP)の文脈における構造パラメータとして非常に成功したことが証明されている。 ここでは、新しいしきい値の概念を通じて、木とハイパーツリーの幅を拡大する。 我々は、閾値木幅とハイパーツリー幅を計算するための効率的な理論的アルゴリズムと経験的アルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 37.90910578253212
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Treewidth and hypertree width have proven to be highly successful structural parameters in the context of the Constraint Satisfaction Problem (CSP). When either of these parameters is bounded by a constant, then CSP becomes solvable in polynomial time. However, here the order of the polynomial in the running time depends on the width, and this is known to be unavoidable; therefore, the problem is not fixed-parameter tractable parameterized by either of these width measures. Here we introduce an enhancement of tree and hypertree width through a novel notion of thresholds, allowing the associated decompositions to take into account information about the computational costs associated with solving the given CSP instance. Aside from introducing these notions, we obtain efficient theoretical as well as empirical algorithms for computing threshold treewidth and hypertree width and show that these parameters give rise to fixed-parameter algorithms for CSP as well as other, more general problems. We complement our theoretical results with experimental evaluations in terms of heuristics as well as exact methods based on SAT/SMT encodings.
• Abstract（参考訳）: treewidthとhypertree widthは制約満足度問題(csp)の文脈で非常に成功した構造パラメータであることが証明されている。 これらのパラメータのいずれかが定数で有界であれば、CSPは多項式時間で解ける。 しかし、実行時間における多項式の順序は幅に依存し、これは避けられないことが知られているので、これらの幅測度のどちらでもパラメータをパラメータ化できない。 ここでは、新しいしきい値の概念を通じて、木と高木幅の強化を導入し、関連する分解を、与えられたCSPインスタンスの解決に関連する計算コストに関する情報に考慮する。 これらの概念の導入以外にも,しきい値木幅とハイパーツリー幅を計算するための効率的な理論アルゴリズムと経験的アルゴリズムを求め,これらのパラメータが csp の固定パラメータアルゴリズムや,より一般的な問題を引き起こすことを示した。 我々は,sat/smtエンコーディングに基づく厳密な手法とヒューリスティックスの観点からの実験的評価で理論的結果を補完する。

関連論文リスト

• Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
  本研究では,2次非制約二項最適化問題に対して,古典分枝および有界解法について記述し,実験的に検証する。 本稿では,Isingモデルに対して提案した文献から,低コストで実装可能なバウンダリを利用する。 本稿では,ソルバ性能向上に使用される高性能コンピューティングとオペレーション研究の様々な技術について詳述する。
  論文  参考訳（メタデータ） (2024-07-29T17:13:01Z)
• Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? [21.10339925217772]
  プログラムのルール構造上での解離的ASPの構造パラメータの分類に対処する。 我々は、その範囲で最も顕著なパラメータに対して、二重指数下界を提供する。 本研究は, 通常のプログラムから解離プログラムへの新規な縮小に頼って, 深部硬度調査を行う。
  論文  参考訳（メタデータ） (2024-02-05T21:51:36Z)
• Optimal Transport for Measures with Noisy Tree Metric [29.950797721275574]
  木メートル空間上での確率測度に対する最適輸送問題について検討する。 一般に、1つの空間でサポートされている測度であっても、このアプローチは計算が難しい。 我々は、ロバスト OT が計量特性を満たすことを示し、負の定値であることを示す。
  論文  参考訳（メタデータ） (2023-10-20T16:56:08Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Solving Projected Model Counting by Utilizing Treewidth and its Limits [23.81311815698799]
  予測モデルカウント(PMC)を解く新しいアルゴリズムを提案する。 いわゆる「ツリー幅」が最も顕著な構造パラメータの1つであるという観測から着想を得て,本アルゴリズムは入力インスタンスの一次グラフの小さなツリー幅を利用する。
  論文  参考訳（メタデータ） (2023-05-30T17:02:07Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。 パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。 提案手法はRパッケージプローブに実装されている。
  論文  参考訳（メタデータ） (2022-09-16T19:15:50Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• Adaptive Subcarrier, Parameter, and Power Allocation for Partitioned Edge Learning Over Broadband Channels [69.18343801164741]
  パーティショニングエッジ学習(PARTEL)は、無線ネットワークにおいてよく知られた分散学習手法であるパラメータサーバトレーニングを実装している。 本稿では、いくつかの補助変数を導入してParticleELを用いてトレーニングできるディープニューラルネットワーク(DNN)モデルについて考察する。
  論文  参考訳（メタデータ） (2020-10-08T15:27:50Z)

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

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