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"”.
-
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 …
-
Variants of stable marriage, algorithms, complexity and structural properties
Το πρόβλημα του Σταθερού Γάμου, προτάθηκε το 1962 από τους David Gale και Lloyd Sharpley. Από τότε, έχουν υπάρξει πολλά θεωρητικά αποτελέσματα αλλά και πολλές εφαρμογές. Επίσης, έχουν προταθεί αρκετές παραλλαγές του προβλήματος, δημιουργώντας μία πολύ ενδιαφέρουσα κλάση προβλημάτων. Η διπλωματική …
-
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 …
-
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 …
-
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 …
-
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.
-
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. …
-
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í …
-
ΕΛΛΕΙΠΤΙΚΗ ΣΥΜΠΕΡΑΣΜΑΤΟΛΟΓΙΑ: ΠΟΛΥΠΛΟΚΟΤΗΤΑ, ΑΛΓΟΡΙΘΜΟΙ, ΣΗΜΑΣΙΟΛΟΓΙΑ
… 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 …
-
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 …
-
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 …
-
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. …
-
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 …
-
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, …
-
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 …
-
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 …
-
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 …
Page 1 of 2