Sökning: "combinatorial problems"

Visar resultat 1 - 5 av 97 avhandlingar innehållade orden combinatorial problems.

  1. 1. Combinatorial Optimization : Three Applications

    Författare :Efraim Laksman; Blekinge Tekniska Högskola; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : Combinatorial optimization is a diverse area of mathematics. It concerns optimization on feasible regions defined by discrete sets, graphs, hypergraphs, matroids, etc. . . LÄS MER

  3. 2. On Some Combinatorial Optimization Problems : Algorithms and Complexity

    Författare :Hannes Uppman; Peter Jonsson; Christer Bäckström; Ulf Nilsson; Stanislav Živný; Linköpings universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computational complexity; optimization; constraint satisfaction problem;

    Sammanfattning : This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems.A constraint language consists of a domain and a set of relations on the domain. For each such language there is a constraint satisfaction problem (CSP). LÄS MER

  4. 3. Combinatorial Slice Theory

    Författare :Mateus de Oliveira Oliveira; Karl Meinke; Stefan Arnborg; Barbara König; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Combinatorial Slice Theory; Partial Order Theory of Concurrency; Digraph Width Measures; Equational Logic;

    Sammanfattning : Slices are digraphs that can be composed together to form larger digraphs.In this thesis we introduce the foundations of a theory whose aim is to provide ways of defining and manipulating infinite families of combinatorial objects such as graphs, partial orders, logical equations etc. LÄS MER

  5. 4. Algorithmic Bounds for Presumably Hard Combinatorial Problems

    Författare :Andreas Björklund; Institutionen för datavetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; numerisk analys; system; control; Datalogi; numerical analysis; systems; Computer science; Approximation algorithms; Exact algorithms; NP-hard problems; Algorithm theory; kontroll;

    Sammanfattning : In this thesis we present new worst case computational bounds on algorithms for some of the most well-known NP-complete and #P-complete problems and their optimization variants. We consider graph problems like Longest Path, Maximum Cut, Number of Perfect Matchings, Chromatic and Domatic Number, as well as Maximum k-Satisfiability and Set Cover. LÄS MER

  7. 5. Analysis of Algorithms for Combinatorial Auctions and Related Problems

    Författare :Kidane Asrat Ghebreamlak; Svante Janson; Arne Andersson; Anders Johansson; Uppsala universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; combinatorial auctions; approximation algorithm; greedy algorithm; optimal strategy; MATHEMATICS; MATEMATIK;

    Sammanfattning : The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction. LÄS MER