Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 22 for “"Algorithms complexity"”.

  1. Combinatorial and exchange markets: Algorithms, complexity, and applications

    … of agents is a constant. - Nash equilibria. The complexity of 2-player Nash equilibrium is by now well understood. Our contribution is on settling the complexity of finding equilibria with special properties on multi-player games. We show that the following decision versions of 3-Nash are …

    gatech Repository record for Combinatorial and exchange markets: Algorithms, complexity, and applications (opens in a new tab)

  2. Variants of stable marriage, algorithms, complexity and structural properties

    Το πρόβλημα του Σταθερού Γάμου, προτάθηκε το 1962 από τους David Gale και Lloyd Sharpley. Από τότε, έχουν υπάρξει πολλά θεωρητικά αποτελέσματα αλλά και πολλές εφαρμογές. Επίσης, έχουν προταθεί αρκετές παραλλαγές του προβλήματος, δημιουργώντας μία πολύ ενδιαφέρουσα κλάση προβλημάτων. Η διπλωματική …

    athens Repository record for Variants of stable marriage, algorithms, complexity and structural properties (opens in a new tab)

  3. On Multistage Stochastic and Distributionally Robust Optimization: New Algorithms, Complexity Analysis, and Performance Comparison

    … We develop dual dynamic programming (DDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. Several interesting classes of MSO problems are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of …

    gatech Repository record for On Multistage Stochastic and Distributionally Robust Optimization: New Algorithms, Complexity Analysis, and Performance Comparison (opens in a new tab)

  4. Análise e comparação entre algoritmos de percolação

    … this work, we study and compare two percolation algorithms, one of then elaborated by Elias, and the other one by Newman and Ziff, using theorical tools of algorithms complexity and another algorithm that makes an experimental comparation. This work is divided in three chapters. The first one …

    brazil-ufrn Repository record for Análise e comparação entre algoritmos de percolação (opens in a new tab)

  5. Computing with Polynomials over Composites

    … bounds for circuits with Mod gates in circuit complexity. Proof techniques that work well for primes break down over composites. Moreover, in some cases, the problem for composites turns out to be very different from the prime case. Making progress on these problems seems to require a better …

    gatech Repository record for Computing with Polynomials over Composites (opens in a new tab)

  6. MEASURES AND ALGORITHMS FOR THE EXACT SATISFIABILITY PROBLEM AND ITS VARIANTS

    … are at least NP-hard. We propose faster exact algorithms to solve these problems, beating the current state of the art algorithms. We either design a new algorithm using a nonstandard measure, or stick to the standard measure and use other nontrivial results to aid us.

    nus Repository record for MEASURES AND ALGORITHMS FOR THE EXACT SATISFIABILITY PROBLEM AND ITS VARIANTS (opens in a new tab) Download file for MEASURES AND ALGORITHMS FOR THE EXACT SATISFIABILITY PROBLEM AND ITS VARIANTS (opens in a new tab)

  7. On the interaction of function, constraint and complexity in evolutionary systems

    … evolution contains a general trend of increasing complexity of the most complex organisms. But artificial evolution experiments based on the mechanisms described in the current theory generally fail to reproduce this trend; instead, they commonly show systematic trends of complexity minimisation. …

    soton Download PDF for On the interaction of function, constraint and complexity in evolutionary systems (opens in a new tab)

  8. Evoluční algoritmy v úloze booleovské splnitelnosti

    Cílem této diplomové práce je najít heuristiku řešící SAT problém pomocí evolučního algoritmu. Jsou zde uvedeny přístupy k řešení SAT problému a různé varianty k evolučním algoritmům, které jsou relevantní k danému tématu. Následně je popsaná implementace lineárního genetického programování …

    brno-tech Repository record for Evoluční algoritmy v úloze booleovské splnitelnosti (opens in a new tab)

  9. ΕΛΛΕΙΠΤΙΚΗ ΣΥΜΠΕΡΑΣΜΑΤΟΛΟΓΙΑ: ΠΟΛΥΠΛΟΚΟΤΗΤΑ, ΑΛΓΟΡΙΘΜΟΙ, ΣΗΜΑΣΙΟΛΟΓΙΑ

    … ASPECTS. WE PROVIDE AN ANALYSIS OF THE COMPLEXITY OF PROPOSITIONAL DISJUNCTION FREE DEFAULT THEORIES AND PROVE THAT EVEN IN THE CASE OF THEORIES WITHOUT PREREQUISITES, THE PROBLEM OF DETERMINING WHETHER AN EXTENSION EXISTS IS NP-COMPLETE. THIS RESULT IS OBTAINED BY TRANSFORMING …

    greece Repository record for ΕΛΛΕΙΠΤΙΚΗ ΣΥΜΠΕΡΑΣΜΑΤΟΛΟΓΙΑ: ΠΟΛΥΠΛΟΚΟΤΗΤΑ, ΑΛΓΟΡΙΘΜΟΙ, ΣΗΜΑΣΙΟΛΟΓΙΑ (opens in a new tab)

  10. Models and Algorithms for Real-Time Systems

    We apply the framework of parameterized algorithms to the FP (fixed-priority) and EDF (earliest- deadline-first) scheduling of recurrent (periodic and sporadic) task systems in a preemptive uniprocessor environment, which are fundamental models in real-time scheduling theory. We identify parameters …

    wustl Repository record for Models and Algorithms for Real-Time Systems (opens in a new tab)

  11. Geometric and Combinatorial Problems of Matching and Partitioning in Theoretical Computer Science

    … that remained open regarding algorithmic complexity and study the minimal and maximal outcome of the game under the assumptions that both players play optimally. We consider these questions in different game modi. 3\. Pareto Optimal Matchings are a concept used in economics and game …

    fu-berlin Repository record for Geometric and Combinatorial Problems of Matching and Partitioning in Theoretical Computer Science (opens in a new tab)

  12. Balancing Branching and Pathwidth: Threshold-Based Approaches for Exponential Algorithms

    We consider exponential-time algorithms for NP-hard problems that combine a pathwidth-based approach and a branching approach. In this context, we investigate how a running time analysis can decide thresholds to balance the two methods, thereby improving the running times for such NP-hard problems. …

    unsw Repository record for Balancing Branching and Pathwidth: Threshold-Based Approaches for Exponential Algorithms (opens in a new tab)

  13. Variants of Pseudo-deterministic Algorithms and Duality in TFNP

    … introduce a new notion of ``faux-deterministic'' algorithms for search problems in query complexity. Roughly, for a search problem $\cS$, a faux-deterministic algorithm is a probability distribution $\mathcal{A}$ over deterministic algorithms $A\in \mathcal{A}$ such that no computationally bounded …

    waterloo Repository record for Variants of Pseudo-deterministic Algorithms and Duality in TFNP (opens in a new tab)

  14. Mathematical Foundations and Algorithms for Clique Relaxations in Networks

    … by generalizations of cliques, as well as algorithms to find such objects in a network. Cliques are a model of an ideal group with roots in social network analysis. They have since found applications as a part of grouping mechanisms in computer vision, coding theory, experimental design, …

    tamu Repository record for Mathematical Foundations and Algorithms for Clique Relaxations in Networks (opens in a new tab)

  15. Information, complexity and structure in convex optimization

    … performance of large-scale convex optimization algorithms. Classical theory of oracle complexity, first proposed by Nemirovski and Yudin in 1983, successfully established the worst-case behavior of methods based on local oracles (a generalization of first-order oracle for smooth functions) for …

    gatech Repository record for Information, complexity and structure in convex optimization (opens in a new tab)

  16. Packing Unit Disks

    … to guide both disk selection and colouring. The complexity of implementing many of the constructions used in our proofs is dominated by a lattice positioning step. As such, we discuss the algorithmic issues involved in positioning lattices as required by each of our proofs. In particular, we show …

    waterloo Repository record for Packing Unit Disks (opens in a new tab)

  17. Homomorphisms of (j, k)-mixed graphs

    A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed …

    uvic Repository record for Homomorphisms of (j, k)-mixed graphs (opens in a new tab)

Page 1 of 2