Sökning: "Approximability"

Visar resultat 11 - 12 av 12 avhandlingar innehållade ordet Approximability.

  1. 11. Algorithmic Graph Problems - From Computer Networks to Graph Embeddings

    Författare :Martin Wahlén; Data Vetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Approximation Algorithms; Exact Algorithms; Time Complexity; Broadcasting;

    Sammanfattning : This dissertation is a contribution to the knowledge of the computational complexity of discrete combinatorial problems. 1. The first problem that we consider is to compute the maximum independent set of a box graph, that is, given a set of orthogonal boxes in the plane compute the largest subset such that no boxes in the subset overlap. LÄS MER

  3. 12. Conditional Inapproximability and Limited Independence

    Författare :Per Austrin; Johan Håstad; Ryan O'Donnell; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computer science; Datalogi;

    Sammanfattning : Understanding the theoretical limitations of efficient computation is one of the most fundamental open problems of modern mathematics. This thesis studies the approximability of intractable optimization problems. In particular, we study so-called Max CSP problems. LÄS MER