Sökning: "Approximationsalgoritm"

Hittade 4 avhandlingar innehållade ordet Approximationsalgoritm.

  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

  3. 2. Efficient Algorithms for Graph-Theoretic and Geometric Problems

    Författare :Peter Floderus; Matematik (naturvetenskapliga fakulteten); []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : This thesis studies several different algorithmic problems in graph theory and in geometry. The applications of the problems studied range from circuit design optimization to fast matrix multiplication. First, we study a graph-theoretical model of the so called ''firefighter problem''. LÄS MER

  4. 3. Macroscopic Modeling of Metabolic Reaction Networks and Dynamic Identification of Elementary Flux Modes by Column Generation

    Författare :Hildur Æsa Oddsdóttir; Anders Forsgren; Bernhard Palsson; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Metabolic Network; Optimization; Robust Optimization; Least-squares; Column Generation; Modeling; Algorithm; Elementary Flux Mode; Metabolic Flux Analysis; Chinese Hamster Ovary Cell; Amino Acid Metabolism; Tillämpad matematik och beräkningsmatematik; Applied and Computational Mathematics;

    Sammanfattning : In this work an intersection between optimization methods and animal cell culture modeling is considered. We present optimization based methods for analyzing and building models of cell culture; models that could be used when designing the environment cells are cultivated in, i.e., medium. LÄS MER

  5. 4. Toward Robust Optimization of Adaptive Radiation Therapy

    Författare :Michelle Böck; Anders Forsgren; Minsun Kim; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; optimization; adaptive radiation therapy; radiation therapy treatment planning; uncertainty; robust optimization; stochastic programming; Tillämpad matematik och beräkningsmatematik; Applied and Computational Mathematics;

    Sammanfattning : Adaptive radiation therapy is an evolving cancer treatment approach which relies on adapting the treatment plan in response to patient-specific interfractional geometric variations occurring during the fractionated treatment. If those variations are not addressed through adaptive replanning, the resulting treatment quality may be compromised. LÄS MER