#### 論文の概要: Solving Infinite-Domain CSPs Using the Patchwork Property

• arxiv url: http://arxiv.org/abs/2107.01428v1
• Date: Sat, 3 Jul 2021 13:04:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-06 14:48:05.874652
• Title: Solving Infinite-Domain CSPs Using the Patchwork Property
• Title（参考訳）: パッチワーク特性を用いた無限領域CSPの解法
• Authors: Konrad K. Dabrowski and Peter Jonsson and Sebastian Ordyniak and George Osipov
• Abstract要約: 制約問題(CSP)は、コンピュータ科学とAIにおいて重要な応用である。 非常に成功したアプローチは、基礎となる原始グラフのツリー幅を束縛することである。 基本関係がパッチワーク特性を持つCSPに対して、これを$f(w)cdot nO(1)$に制限する。
• 参考スコア（独自算出の注目度）: 17.101875753030754
• Abstract: The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau [J. Comput. System. Sci. 79(1), 2013] and Huang et al. [Artif. Intell. 195, 2013] proved that CSP$(\Gamma)$ can be solved in $n^{f(w)}$ time (where $n$ is the size of the instance, $w$ is the treewidth of the primal graph and $f$ is a computable function) for certain classes of constraint languages $\Gamma$. We improve this bound to $f(w) \cdot n^{O(1)}$, where the function $f$ only depends on the language $\Gamma$, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmau's algorithm but not by ours, and we begin investigating ways of generalising our results to larger families of languages. We also analyse our algorithm with respect to its running time and show that it is optimal (under the Exponential Time Hypothesis) for certain languages such as Allen's Interval Algebra.
• Abstract（参考訳）: 制約満足度問題(CSP)は、コンピュータ科学とAIにおいて重要な応用である。 特に、無限ドメインCSPは時空間推論のようなAIのサブ領域で集中的に使用されている。 制約満足度は計算的に難しい問題であるため、効率的に解くことができる制限された問題を特定することに多くの研究が費やされてきた。 これを行う一つの方法は変数と制約の相互作用を制限することであり、非常に成功したアプローチは、基礎となる原始グラフのツリー幅を束縛することである。 Bodirsky & Dalmau [J. Comput] システム。 Sci 79(1), 2013]およびHuang et al。 [芸術] インテリ。 195, 2013] は csp$(\gamma)$ が $n^{f(w)$ time (ここで $n$ はインスタンスのサイズ、$w$ はプリマルグラフのツリー幅、$f$ は計算可能な関数) で制約言語のクラス $\gamma$ で解くことができることを証明した。 我々はこれを$f(w) \cdot n^{O(1)}$に制限し、基本関係がパッチワーク特性を持つCSPに対して、関数$f$は言語$\Gamma$にのみ依存する。 したがって、そのような問題は固定パラメータ抽出可能であり、我々のアルゴリズムは前よりも漸近的に高速である。 さらに、我々のアプローチは二項制約に制限されないので、Huangらよりも厳密な問題のクラスに適用できる。 しかしながら、Bodirsky & Dalmau のアルゴリズムではカバーできるが我々のアルゴリズムではカバーできない自然問題が存在し、我々はその結果をより大きな言語族に一般化する方法を探り始める。 また、実行時間に関してアルゴリズムを分析し、AllenのInterval Algebraのような特定の言語に対して(指数時間仮説の下で)最適であることを示す。

#### 関連論文リスト

• Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning [9.594432031144716]
アレンの区間代数は質的時間的推論において最もよく知られた計算の1つである。 NPハードな定性推論問題を解くための新しい枠組みを提案する。 我々はアレンの区間代数に対して$O*((fraccnlogn)n)$の大きな改善を得る。
論文  参考訳（メタデータ） (2023-05-25T11:45:12Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications [0.0]
有向非巡回グラフ(DAG)問題に対する動的プログラミング手法のための量子アルゴリズムを提案する。 OR, AND, NAND, MAX, MIN 関数を主な遷移ステップとする問題を解くことができることを示す。
論文  参考訳（メタデータ） (2022-12-29T19:07:39Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• A Multivariate Complexity Analysis of Qualitative Reasoning Problems [9.594432031144716]
我々は、それぞれ$f(k) cdot 2O(n)$, $f(k)n$, timeで解ける問題のクラス FPE と XE を紹介する。 有効幅$k$の部分順序時間問題は16kn$時間で解決可能であり,XEに含まれることを示す。 また、アレンの区間代数のネットワーク整合性問題は、$k$以上と重複しないが、$(2nk)2k cdot 2n$timeで解決可能であり、その中に含まれることを示す。 論文 参考訳（メタデータ） (2022-09-30T07:29:53Z) • Efficient Algorithms for Planning with Participation Constraints [74.74967476995572] 我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。 論文 参考訳（メタデータ） (2022-05-16T15:47:41Z) • Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445] citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。 一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。 本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
論文  参考訳（メタデータ） (2020-06-22T17:38:14Z)