Sökning: "Constraint Satisfaction Problem"

Visar resultat 1 - 5 av 19 avhandlingar innehållade orden Constraint Satisfaction Problem.

  1. 1. Beating a Random Assignment Approximating Constraint Satisfaction Problems

    Detta är en avhandling från Stockholm : KTH

    Författare :Gustav Hast; KTH.; [2005]
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Datalogi; TECHNOLOGY Information technology Computer science Computer science; TEKNIKVETENSKAP Informationsteknik Datavetenskap Datalogi;

    Sammanfattning : An instance of a Boolean constraint satisfaction problem, CSP, consists of a set of constraints acting over a set of Boolean variables. The objective is to find an assignment to the variables that satisfies all the constraints. LÄS MER

  2. 2. Constructing Algorithms for Constraint Satisfaction and Related Problems Methods and Applications

    Detta är en avhandling från Institutionen för datavetenskap

    Författare :Ola Angelsmark; Linköpings universitet.; Linköpings universitet.; [2005]
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; constraint satisfaction; CSP; graph problems; algorithm construction; computational complexity; microstructures; graph colouring; decision problems; optimisation problems; quantum computing; molecular computing; TECHNOLOGY Information technology Computer science; TEKNIKVETENSKAP Informationsteknik Datavetenskap;

    Sammanfattning : In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. LÄS MER

  3. 3. Hardness of Constraint Satisfaction and Hypergraph Coloring Constructions of Probabilistically Checkable Proofs with Perfect Completeness

    Detta är en avhandling från Stockholm : KTH Royal Institute of Technology

    Författare :Sangxia Huang; KTH.; [2015]
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Combinatorial optimization; approximation; inapproximability; hardness; probabilistically checkable proofs; pcp; perfect completeness; boolean constraint satisfaction problem; csp; graph coloring; hypergraph coloring; direct sum; superposition; label cover; Computer Science; Datalogi;

    Sammanfattning : A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. LÄS MER

  4. 4. Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction

    Detta är en avhandling från Stockholm : Numerical Analysis and Computer Science (NADA), Stockholm University

    Författare :Cenny Wenner; Stockholms universitet.; [2014]
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computer Science; Datalogi; Optimization; NP; Approximation; Approximability; Inapproximability; Constraint Satisfaction; CSP; Boolean Analysis; Satisfiability; SAT; Acyclic Subgraph; Betweenness; Unique Games; datalogi; Computer Science; Combinatorial Optimization; Complexity Theory; Computational Hardness; Kombinatorisk optimering; Komplexitetsteori; Beräkningsteori; Approximerbarhet; Beräkningssvårighet; Optimering; Vilkorssatisfiering; Vilkorsuppfyllning; Vilkorstillfredställand;

    Sammanfattning : Kombinatoriska optimering inkluderar naturliga uppgifter såsom att hitta den snabbaste vägen till sitt arbetet, att schemalägga jobb hos specialister, eller att placera hållplatser för att minimera resenärers restid.Vi begränsar vi oss till de problem i vilket man ges en samling vilkor på variablermed målet att hitta en tilldelning av variablerna uppfyllandes så många som möjligt av vilkoren;så kallade Vilkorsuppfyllningsproblem (eng: Constraint Satisfaction Problems, CSPs). LÄS MER

  5. 5. Aspects of a Constraint Optimisation Problem

    Detta är en avhandling från Linköping : Linköping University Electronic Press

    Författare :Johan Thapper; Linköpings universitet.; Linköpings universitet.; [2010]
    Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; TECHNOLOGY; TEKNIKVETENSKAP;

    Sammanfattning : In this thesis we study a constraint optimisation problem called the maximum solution problem, henceforth referred to as Max Sol. It is defined as the problem of optimising a linear objective function over a constraint satisfaction problem (Csp) instance on a finite domain. LÄS MER