Solving Infinite-Domain CSPs Using the Patchwork Property

• URL: http://arxiv.org/abs/2107.01428v1
• Date: Sat, 3 Jul 2021 13:04:41 GMT
• Title: Solving Infinite-Domain CSPs Using the Patchwork Property
• Authors: Konrad K. Dabrowski and Peter Jonsson and Sebastian Ordyniak and George Osipov
• Abstract summary: The constraint problem (CSP) has important applications in computer science and AI. A highly successful approach is to bound the treewidth of the underlying primal graph. We improve this bound to $f(w)cdot nO(1)$, for CSPs whose basic relations have patchwork property.
• Score: 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.

Related papers

• Fast decision tree learning solves hard coding-theoretic problems [7.420043502440765]
  We show that improvement of Ehrenfeucht and Haussler's algorithm will yield $O(log n)$-approximation algorithms for $k$-NCP. This can be interpreted as a new avenue for designing algorithms for $k$-NCP, or as one for establishing the optimality of Ehrenfeucht and Haussler's algorithm.
  arXiv  Detail & Related papers  (2024-09-19T21:40:57Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  We study a new class of MDPs that employs multinomial logit (MNL) function approximation to ensure valid probability distributions over the state space. introducing the non-linear function raises significant challenges in both computational and statistical efficiency. We propose an algorithm that achieves the same regret with only $mathcalO(1)$ cost.
  arXiv  Detail & Related papers  (2024-05-27T11:31:54Z)
• Chasing Convex Functions with Long-term Constraints [11.029788598491077]
  We introduce and study a family of online metric problems with long-term constraints. Such problems can find a wide array of applications to online resource allocation in sustainable energy/computing systems.
  arXiv  Detail & Related papers  (2024-02-21T18:51:42Z)
• Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning [9.594432031144716]
  Allen's interval algebra is one of the most well-known calculi in qualitative temporal reasoning. We propose a novel framework for solving NP-hard qualitative reasoning problems. We obtain a major improvement of $O*((fraccnlogn)n)$ for Allen's interval algebra.
  arXiv  Detail & Related papers  (2023-05-25T11:45:12Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  We propose a provably efficient reinforcement learning algorithm (both computationally and statistically) with general value function approximations. Our algorithm achieves reasonable regret bounds when applied to both the linear setting and the sparse high-dimensional linear setting.
  arXiv  Detail & Related papers  (2023-02-22T20:21:25Z)
• Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications [0.0]
  We present a quantum algorithm for the dynamic programming approach for problems on directed acyclic graphs (DAGs) We show that we can solve problems that use OR, AND, NAND, MAX, and MIN functions as the main transition steps.
  arXiv  Detail & Related papers  (2022-12-29T19:07:39Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022] In this problem, a principal chooses actions in a decision process, resulting in separate utilities for the principal and the agent. We provide the first-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $varepsilon$-approximation was known.
  arXiv  Detail & Related papers  (2022-05-16T15:47:41Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.