Deterministic and randomized approaches to constraint satisfaction problems

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Wang, Yuyan
• dc.date.accessioned 2025-10-13T14:27:29Z
• dc.date.available 2025-10-13T14:27:29Z
• dc.date.issued 2025
• dc.description Tutor: Victor Dalmau
• dc.description Treball de fi de grau en Enginyeria Matemàtica en Ciència de Dades
• dc.description.abstract 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.ENG
• dc.description.abstract Aquesta tesi explora algoritmes per a la resolucio de Problemes de Satisfacció de Restriccions (CSP), amb un emfasi particular en els algoritmes randomitzats. L’estudi es centra en instancies de CSP que combinen tres classes especıfiques de restriccions: restriccions de valor (Value Restriction Constraints), restriccions 2-Fan i restriccions de permutacio binaria (Binary Permutation Constraints). Aquestes constitueixen un dels fragments tractables mes coneguts dins del panorama general dels CSP binaris. Per establir una base solida, la tesi introdueix primer aquestes famílies de restriccions i desenvolupa algoritmes deterministes per a cadascuna, aprofundint en la comprensio de les seves propietats estructurals. La contribució principal consisteix en el disseny i l’analisi d’un algoritme randomitzat general que resol instancies combinades d’aquestes restriccions amb un temps esperat d’execució polinomic. Inspirat en tècniques com l’algoritme de Papadimitriou per al problema 2-SAT, aquest algoritme demostra com l’aleatoritzacio pot trobar solucions de ́manera efectiva per a aquest tipus de CSP. Els resultats s’alineen amb els treballs teorics previs sobre classes tractables de CSP, i aporten una solucio algorítmica per a aquest important subconjunt de problemes.CAT
• dc.identifier.uri http://hdl.handle.net/10230/71491
• dc.language.iso eng
• dc.rights Llicència CC Reconeixement-NoComercial-SenseObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0)
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.rights.uri https://creativecommons.org/licenses/by-nc-nd/4.0/
• dc.subject.other Intel·ligència artificial
• dc.title Deterministic and randomized approaches to constraint satisfaction problems
• dc.type info:eu-repo/semantics/bachelorThesis