Sökning: "approximability"

Visar resultat 1 - 5 av 12 avhandlingar innehållade ordet approximability.

  1. 1. 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

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

  4. 3. Grothendieck's approximation property and approximability in some operator topologies

    Författare :Anders Pelander; Uppsala universitet; []
    Nyckelord :;

    Sammanfattning : .... LÄS MER

  5. 4. Approximation and Online Algorithms with Applications in Computational Biology and Computational Geometry

    Författare :Mia Persson; Data Vetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; numerisk analys; system; systems; control; Datalogi; numerical analysis; broadcasting; polygon exploration; robotics; Mathematics; Matematik; Computer science; clique partition; clustering; computational complexity; computational geometry; computational biology; online algorithm; kontroll; approximation algorithm;

    Sammanfattning : The main contributions of this thesis are in the area of approximation and online algorithm design and derivation of lower bounds on the approximability for a number of combinatorial optimization problems with applications in computational biology and computational geometry. Approximation and online algorithms are fundamental tools used to deal with computationally hard problems and problems in which the input is gradually disclosed over time. LÄS MER

  7. 5. 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