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"”.

  1. 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 …

    ubc Repository record for Performance modelling and automated algorithm design for NP-hard problems (opens in a new tab) Download PDF for Performance modelling and automated algorithm design for NP-hard problems (opens in a new tab)

  2. 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 …

    birmingham Download PDF for Fitness landscape analysis of a class of np-hard problems (opens in a new tab)

  3. 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 …

    uiuc Repository record for Linear and nonlinear semidefinite relaxations of some NP-hard problems (opens in a new tab)

  4. 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 …

    catania Repository record for Learning NP-hard problems on networks using Geometric Deep Learning (opens in a new tab)

  5. 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 …

    texas-state Repository record for Scalable and Robust Solutions for NP-Hard Problems in Large Signed Networks (opens in a new tab)

  6. 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 …

    colostate Repository record for An analysis of combinatorial search spaces for a class of NP-hard problems (opens in a new tab)

  7. 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. …

    tamu Repository record for Measure-Driven Algorithm Design and Analysis: A New Approach for Solving NP-hard Problems (opens in a new tab)

  8. 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, …

    waterloo Repository record for A Blueprint for Semidefinite Relaxations of Binary-Constrained Quadratic Programs Computing tight bounds on NP-hard problems using ADMM (opens in a new tab)

  9. 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 …

    tamu Repository record for Randomized and Deterministic Parameterized Algorithms and Their Applications in Bioinformatics (opens in a new tab)

  10. 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 …

    tamu Repository record for Parameterized algorithms and computational lower bounds: a structural approach (opens in a new tab)

  11. 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: …

    tamu Repository record for Kernelization and Enumeration: New Approaches to Solving Hard Problems (opens in a new tab)

  12. 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 …

    calpoly Repository record for Solving Chromatic Number with Quantum Search and Quantum Counting (opens in a new tab)

  13. 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.

    jhu Repository record for Algorithms and Hardness Results for Compressing Graphs with Distance Constraints (opens in a new tab)

  14. 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)

  15. 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 …

    unlv Repository record for A Branch and Bound Method for Sum of Completion Permutation Flow Shop (opens in a new tab) Download PDF for A Branch and Bound Method for Sum of Completion Permutation Flow Shop (opens in a new tab)

  16. 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 …

    brazil-uerj Repository record for Uso da metaheurística de busca em vizinhança variável para redução de largura de banda em matrizes esparsas (opens in a new tab)

  17. ΤΕΧΝΙΚΕΣ ΣΧΕΔΙΑΣΜΟΥ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΚΑΙ Η ΕΦΑΡΜΟΓΗ ΤΟΥΣ ΣΕ ΠΡΟΒΛΗΜΑΤΑ ΓΡΑΦΩΝ

    … 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 …

    greece Repository record for ΤΕΧΝΙΚΕΣ ΣΧΕΔΙΑΣΜΟΥ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΚΑΙ Η ΕΦΑΡΜΟΓΗ ΤΟΥΣ ΣΕ ΠΡΟΒΛΗΜΑΤΑ ΓΡΑΦΩΝ (opens in a new tab)

  18. 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 …

    concordia Download PDF for Symmetry in combinatorial optimization (opens in a new tab)

Page 1 of 8