Repositori Digital de la UPF
Carregant...
This thesis explores algorithmic approaches to solving Constraint Satisfaction Problems (CSPs), with a particular focus on randomized algorithms. The study targets CSP instances that combine three specific classes of constraints: Value Restriction Constraints, 2-Fan Constraints, and Binary Permutation Constraints. These form one of the largest known tractable fragments of the general binary CSP landscape.
To build a solid foundation, the thesis first introduces these constraint families and develops deterministic algorithms for each, gaining deeper insights into their structural properties. The core contribution is the design and analysis of a general randomized algorithm that solves combined instances of these constraints with polynomial expected runtime. Inspired by techniques such as Papadimitriouasˆ random walk for 2-SAT, this approach demonstrates how randomization can effectively find a solution for such CSPs. The results align with and extend prior theoretical work on tractable CSP classes, providing an algorithmic solution for this important subclass of problems.
(2025)