論文の概要: 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
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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のような特定の言語に対して(指数時間仮説の下で)最適であることを示す。
関連論文リスト
- Fast decision tree learning solves hard coding-theoretic problems [7.420043502440765]
我々は、Ehrenfeucht と Haussler のアルゴリズムの改善により、$k$-NCP に対して$O(log n)$-approximation アルゴリズムが得られることを示す。
これは、$k$-NCPのアルゴリズムを設計するための新しい道、あるいはEhrenfeucht と Haussler のアルゴリズムの最適性を確立するための道と解釈できる。
論文 参考訳（メタデータ） (2024-09-19T21:40:57Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
本稿では,MNL関数近似を用いたMDPの新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。
非線型関数の導入は、計算効率と統計効率の両方において大きな課題を提起する。
我々は,$mathcalO(1)$$コストで同じ後悔を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T11:31:54Z) - Chasing Convex Functions with Long-term Constraints [11.029788598491077]
我々は,長期的制約を伴うオンライン計量問題群を紹介し,研究する。
このような問題は、持続可能なエネルギー/計算システムにおけるオンラインリソース割り当てへの幅広い応用を見出すことができる。
論文 参考訳（メタデータ） (2024-02-21T18:51:42Z) - 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) - Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。
この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。
有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
論文 参考訳（メタデータ） (2022-05-16T15:47:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。