Sökning: "constraint satisfaction"

Visar resultat 1 - 5 av 41 avhandlingar innehållade orden constraint satisfaction.

1. 1. Approximate constraint satisfaction

   Författare :Lars Engebretsen; KTH; []
   Nyckelord :;

   Sammanfattning : .... LÄS MER

3. 2. Beating a Random Assignment : Approximating Constraint Satisfaction Problems

   Författare :Gustav Hast; Johan Håstad; Uri Zwick; KTH; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Datalogi; Computer science; 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

4. 3. Constructing Algorithms for Constraint Satisfaction and Related Problems : Methods and Applications

   Författare :Ola Angelsmark; Peter Jonsson; Brahim Hnich; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; constraint satisfaction; CSP; graph problems; algorithm construction; computational complexity; microstructures; graph colouring; decision problems; optimisation problems; quantum computing; molecular computing; Computer science; 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

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

   Författare :Cenny Wenner; Johan Håstad; Viggo Kann; Irit Dinur; Stockholms universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Combinatorial Optimization; Complexity Theory; Approximation; Approximability; Inapproximability; Computational Hardness; NP; Optimization; Constraint Satisfaction; Kombinatorisk optimering; Komplexitetsteori; Beräkningsteori; Approximation; Approximerbarhet; Beräkningssvårighet; NP; Optimering; Vilkorssatisfiering; Vilkorsuppfyllning; Vilkorstillfredställand; datalogi; Computer Science;

   Sammanfattning : Combinatorial optimization include such tasks as finding the quickest route to work, scheduling jobs to specialists, and placing bus stops so as to minimize commuter times. We consider problems where one is given a collection of constraints with the objective of finding an assignment satisfying as many constraints as possible, also known as Constraint Satisfaction Problems (CSPs). LÄS MER

7. 5. Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction

   Författare :Cenny Wenner; Johan Håstad; Irit Dinur; Numerical Analysis and Computer Science (NADA) Faculty of Science Stockholm University; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Optimization; NP; Approximation; Approximability; Inapproximability; Constraint Satisfaction; CSP; Boolean Analysis; Satisfiability; SAT; Acyclic Subgraph; Betweenness; Unique Games; Computer Science; Datalogi;

   Sammanfattning : Problem solving is an integral aspect of modern society and includes such tasks as picking the fastest route to work, optimizing a production line, scheduling computer tasks, placing new bus stops, or picking a meal from available ingredients.We study the hardness of solving Constraint Satisfaction Problems (CSPs). LÄS MER