Sökning: "constraint satisfaction problem"

Visar resultat 6 - 10 av 28 avhandlingar innehållade orden constraint satisfaction problem.

1. 6. Aspects of a Constraint Optimisation Problem

   Författare :Johan Thapper; Peter Jonsson; David Cohen; Linköpings universitet; []
   Nyckelord :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

3. 7. Symmetry Breaking Ordering Constraints

   Författare :Zeynep Kiziltan; Andreas Hamfelt; Toby Walsh; Pedro Meseguer; Uppsala universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Datavetenskap; Constraint satisfaction; constraint programming; modelling; symmetry breaking; global constraints; Datavetenskap; Computer science; Datavetenskap;

   Sammanfattning : Many problems in business, industry, and academia can be modelled as constraint programs consisting of matrices of decision variables. Such “matrix models” often have symmetry. In particular, they often have row and column symmetry as the rows and columns can freely be permuted without affecting the satisfiability of assignments. LÄS MER

4. 8. Hardness of Approximating Constraint Satisfaction Problems and Their Variants in Presence of Additional Structural Assumptions

   Författare :Aleksa Stankovic; Johan Håstad; Per Austrin; Luca Trevisan; KTH; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Hardness of Approximation; Approximation Algorithms; Label Cover; Vertex Cover; Unique Games Conjecture; Max-3-Lin; Universal Factor Graphs; Regular Constraint Satisfaction Problems; Inapproximerbarhet; Approximationsalgoritm; Label Cover; Vertex Cover; Unique Games Conjecture; Max-3-Lin; Universell Faktorgraf; Regelbundna Begränsningsproblem; Datalogi; Computer Science;

   Sammanfattning : This thesis studies how the approximability of some fundamental computational problems is affected by some additional requirements on the structure of the inputs. The problems studied in this thesis belong or are closely related to constraint satisfaction problems (CSPs), which are considered to be one of the most fundamental problems in theoretical computer science. LÄS MER

5. 9. Strong Partial Clones and the Complexity of Constraint Satisfaction Problems : Limitations and Applications

   Författare :Victor Lagerkvist; Peter Jonsson; Christer Bäckström; Nadia Creignou; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

   Sammanfattning : In this thesis we study the worst-case time complexity of the constraint satisfaction problem parameterized by a constraint language (CSP(S)), which is the problem of determining whether a conjunctive formula over S has a model. To study the complexity of CSP(S) we borrow methods from universal algebra. LÄS MER

7. 10. On Some Combinatorial Optimization Problems : Algorithms and Complexity

   Författare :Hannes Uppman; Peter Jonsson; Christer Bäckström; Ulf Nilsson; Stanislav Živný; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computational complexity; optimization; constraint satisfaction problem;

   Sammanfattning : This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems.A constraint language consists of a domain and a set of relations on the domain. For each such language there is a constraint satisfaction problem (CSP). LÄS MER