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 143 for “"NP-hard problems"”.
-
Performance modelling and automated algorithm design for NP-hard problems
… applications, some important classes of problems are NP-complete. Although no worst-case polynomial time algorithm exists for solving them, state-of-the-art algorithms can solve very large problem instances quickly, and algorithm performance varies significantly across instances. In …
-
Fitness landscape analysis of a class of np-hard problems
… of randomly generated instances of a class of NP-hard combinatorial optimisation problems are empirically studied in this research. We believe that the studied properties give insight into the structure of the problem landscape and can be representative of the problem difficulty, in particular …
-
Linear and nonlinear semidefinite relaxations of some NP-hard problems
… bounds and obtain approximate solutions for NP-hard problems. This thesis introduces and studies several novel linear and nonlinear semidefinite relaxation models for some NP-hard problems. We first study the semidefinite relaxation of Quadratic Assignment Problem (QAP) based on matrix …
-
Learning NP-hard problems on networks using Geometric Deep Learning
… networks and their applications. However, many problems on networks remain hard to define formally and even harder to solve exactly (for instance for computational constraints), requiring sub-optimal heuristics. In this work we show how Geometric Deep Learning, the generalization of Deep …
-
Scalable and Robust Solutions for NP-Hard Problems in Large Signed Networks
… to address specific signed graph-related problems. Moreover, existing machine learning models often focus on single-modal approaches, limiting their ability to generalize effectively to new and unseen data distributions. In this dissertation, we introduce three scalable heuristic …
-
An analysis of combinatorial search spaces for a class of NP-hard problems
… are state of the art for many classes of NP-hard combinatorial optimization problems such as maximum k-satisfiability, scheduling, and problems of graph theory. In this thesis we analyze combinatorial search spaces by expanding the objective function into a (sparse) series of basis …
-
Measure-Driven Algorithm Design and Analysis: A New Approach for Solving NP-hard Problems
NP-hard problems have numerous applications in various fields such as networks, computer systems, circuit design, etc. However, no efficient algorithms have been found for NP-hard problems. It has been commonly believed that no efficient algorithms for NP-hard problems exist, i.e., that P6=NP. …
-
A Blueprint for Semidefinite Relaxations of Binary-Constrained Quadratic Programs Computing tight bounds on NP-hard problems using ADMM
… thesis looks at the solution techniques of two NP-hard, large scale problems, the quadratic assignment problem, QAP, and the side chain positioning, SCP, problem. We summarize existing approaches from and look at the two problems in a unified way using a binary-constrained quadratic program, …
-
Randomized and Deterministic Parameterized Algorithms and Their Applications in Bioinformatics
Parameterized NP-hard problems are NP-hard problems that are associated with special variables called parameters. One example of the problem is to find simple paths of length k in a graph, where the integer k is the parameter. We call this problem the p-path problem. The p-path problem is the …
-
Parameterized algorithms and computational lower bounds: a structural approach
Many problems of practical significance are known to be NP-hard, and hence, are unlikely to be solved by polynomial-time algorithms. There are several ways to cope with the NP-hardness of a certain problem. The most popular approaches include heuristic algorithms, approximation algorithms, and …
-
Kernelization and Enumeration: New Approaches to Solving Hard Problems
NP-Hardness is a well-known theory to identify the hardness of computational problems. It is believed that NP-Hard problems are unlikely to admit polynomial-time algorithms. However since many NP-Hard problems are of practical significance, different approaches are proposed to solve them: …
-
COMPLETELY POSITIVE AND CO-POSITIVE PROGRAMMING: APPLICATIONS IN DISRUPTION RISK MANAGEMENT, POST DISASTER HUMANITARIAN LOGISTICS AND HOMELAND SECURITY GAMES
… programs to obtaining bounds to $\mathcal{NP}$-hard problems as well as stochastic optimization problem. There are literature establishing the equivalence between completely/co-positive programs and several classic NP-hard problems, such as nonconvex quadratic problem, maximum stable set …
-
Solving Chromatic Number with Quantum Search and Quantum Counting
… algorithm. Chromatic Number is an example of an NP-Hard problem, which suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can be framed as NP-Hard problems, so any speed-up in the solution of …
-
Algorithms and Hardness Results for Compressing Graphs with Distance Constraints
… consider different versions of graph compression problems, including graph spanners, approximate distance oracles, and Steiner networks. Since these problems are all NP-hard problems, we will mostly focus on designing approximation algorithms and proving inapproximability results.
-
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. …
-
A Branch and Bound Method for Sum of Completion Permutation Flow Shop
… shop problem (F||∑Ci ) belongs to the class of NP-hard problems; finding the optimal solution is thus expected to be highly computational. For each solution our scheme gives an approximation ratio and finds near optimal solutions. Computational results for up to 20 jobs are given for 3 machine …
-
Uso da metaheurística de busca em vizinhança variável para redução de largura de banda em matrizes esparsas
… obtained solutions. PRB belongs to the class of NP-hard problems, so in general the computational time to get exact solutions grows exponentially with the size of the input. As an alternative to the high computational cost of obtaining exact solutions, we propose the use of a variant of the …
-
ΤΕΧΝΙΚΕΣ ΣΧΕΔΙΑΣΜΟΥ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΚΑΙ Η ΕΦΑΡΜΟΓΗ ΤΟΥΣ ΣΕ ΠΡΟΒΛΗΜΑΤΑ ΓΡΑΦΩΝ
… ALGORITHMS AND THEIR APPLICATION TO GRAPH PROBLEMS. MORE PRECISELY: 1. WE PRESENT A DETERMINISTIC TECHNIQUE BASED ON THE DECOMPOSITION OF A PLANAR DIGRAPH INTO SPECIAL OUTERPLANAR SUBGRAPHS CALLED HAMMOCKS. 2. WE PRESENT A PROBABILISTIC TECHNIQUE FOR FINDING PARALLEL APPROXIMATION SOLUTIONS …
-
Symmetry in combinatorial optimization
Integer optimization is in the class of NP-hard problems, and it is very time and memory intensive to find optimal solutions. In this thesis an algorithm will be developed to improve the efficiency in solving a linear integer program if there are symmetries in the problem, that is, variables can be …
Page 1 of 8