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 14 of 14 for “"NP-complete problems"”.
-
An Interactive Tutorial for NP-Completeness
… Complexity Theory, reductions, and the NP-Complete class of problems are considered difficult by students. Numerous algorithm visualizations (AVs) have been developed over the years to portray the dynamic nature of known algorithms commonly taught in undergraduate classes. However, to …
-
Branch decompositions and their applications
Many real-life problems can be modeled as optimization or decision problems on graphs. Also, many of those real-life problems are NP-hard. One traditional method to solve these problems is by branch and bound while another method is by graph decompositions. In the 1980's, Robertson and Seymour …
-
Hybrid solvers for the Boolean Satisfiability problem: an exploration
… (SAT) is one of the most extensively researched NP-complete problems in Computer Science. This thesis focuses on the design of feasible solvers for this problem. A SAT problem instance is a formula in propositional logic. A SAT solver attempts to find a solution for the formula. Our research …
-
Improved Approximation Algorithms for Geometric Packing Problems With Experimental Evaluation
Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first …
-
Distributed SAT solving engine
… problem (SAT) is one of the typical NP-complete problems that have found considerable industrial applications in the past decades. Significant theoretical and practical efforts has been devoted to the research in this particular problem. Recently, with the major architectural shift …
-
Efficient Bandwidth Reservation Strategies for Data Movements on High Performance Networks
… We focus on two important bandwidth reservation problems formulated from the combinations of the requirements from both users and the bandwidth reservation service providers of the HPNs: (i) Problem of scheduling all BRRs in one batch while achieving their best average data transfer earliest …
-
Regularity and removal lemmas and their applications
… giving approximation algorithms for some co-NP-complete problems. We show how to use the Frieze-Kannan regularity lemma to approximate the regularity of a pair of vertex sets. We also show how to quickly find, for each [epsilon]' > [epsilon], an [epsilon]'-regular partition with k parts if …
-
Generalized Satisfiability Problems
… of complexity theory is the classification of problems with respect to their consumption of resources (e.g., running time or required memory). To study the computational complexity (i.e., consumption of resources) of problems, similar problems are grouped into so called complexity classes. …
-
A Hybrid multi-agent architecture and heuristics generation for solving meeting scheduling problem
… enough to be applied as a technology for solving problems in an increasingly wide range of complex applications. The main formal architectures used to describe the relationships between agents in MAS are centralised and distributed architectures. In computational complexity theory, researchers …
-
New techniques for implementing membrane systems
… obtain optimal results when dealing with complex problems. In fact, new scenarios containing P-systems are shown. These scenarios have the transition P-systems working together with other technologies. Furthermore, methodologies and new software are introduced to implement the evolution rules …
-
State estimation and sensor selection in discrete event systems modeled by Petri nets
… dissertation, we focus on two sensor related problems in discrete event systems modeled by Petri nets: (i) State estimation. When only transition sensors are available, sensor information can be very limited because there can be uncertainty due to unobservable events or events that generate …
-
Metaheuristic strategies for scheduling under uncertainty
Scheduling problems are a kind of combinatorial problems that pose a great challenge to Artificial Intelligence researchers, being very hard to solve. They are well-known NP-complete problems which have had a great presence in the literature during the last decades. However, in the classical …
-
Modern Interactive Proofs
… (psdIP): interactive proof systems for search problems where the verifier is guaranteed with high probability to output the same output on different executions. As in the case with classical interactive proofs, the verifier is a probabilistic polynomial time algorithm interacting with an …
-
Unapređenje konstruktivnih heuristika za probleme kombinatorne optimizacije u operacionom menadžmentu
… menadžmentu koji pripadaju klasi složenosti NP. Predstavljen je novi generalizovani konstruktivni algoritam koji omogućava da se raznovrsne heuristike formiraju izborom njegovih argumenata. Takođe je uvedeno opšte okruženje za generisanje permutacija, koje formira vezu između enumeracije …