Sökning: "Aleksa Stankovic"

Hittade 1 avhandling innehållade orden Aleksa Stankovic.

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