Sökning: "csp"

Visar resultat 1 - 5 av 47 avhandlingar innehållade ordet csp.

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

   Författare :Sangxia Huang; Johan Håstad; Rishi Saket; KTH; []
   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

3. 2. 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

4. 3. 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

5. 4. Cost-effective fuel and technology choices in the transportation sector in a future carbon constrained world: Results from the Global Energy Transition (GET) model

   Författare :Maria Grahn; Chalmers tekniska högskola; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; SAMHÄLLSVETENSKAP; SOCIAL SCIENCES; energy prices; CSP; CO2 emissions; hydrogen; CCS; carbon tax; biomass; carbon leakage; liquid biofuels; global energy systems modeling; transportation; passenger vehicles;

   Sammanfattning : This thesis analyzes future fuel and technology choices focusing on transport in a carbon constrained world. The analysis tool used in all five appended papers is the cost-minimizing Global Energy Transition (GET) model. LÄS MER

7. 5. Exploiting Structure in CSP-related Problems

   Författare :Tommy Färnqvist; Peter Jonsson; Miki Hermann; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

   Sammanfattning : In this thesis we investigate the computational complexity and approximability of computational problems from the constraint satisfaction framework. An instance of a constraint satisfaction problem (CSP) has three components; a set V of variables, a set D of domain values, and a set of constraints C. LÄS MER