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 85 for “"NP-complete problems"”.

  1. Learning to solve NP-complete problems

    … decision variant of the TSP, a highly relevant NP-Complete problem. Our model is trained to function as an effective message-passing algorithm in graph in which edges from the input graph communicate with vertices from the input graph for a number of iterations after which the model is asked to …

    brazil-ufrgs Repository record for Learning to solve NP-complete problems (opens in a new tab)

  2. Clustering solutions: a novel approach to solving NP-complete problems

    … we introduce a novel approach to solving MAX-SAT problems. This algorithm clusters good solutions, and restarts the search from the closest feasible configuration to the centroid of each cluster. We call this method Clustered-Landscape Guided Hopping (CLGH). In addition, where clustering does not …

    soton Download PDF for Clustering solutions: a novel approach to solving NP-complete problems (opens in a new tab)

  3. The INDEPENDENT SET Decision Problem is NP-complete

    … the theory of computational complexity. Some problems seemed hard-to-compute, while others were easy. It turned out that many of the hard problems were equally hard in a way that could be precisely specified. They became known as the NP-complete problems. The SATISFIABILITY problem (SAT) was …

    vcu Repository record for The INDEPENDENT SET Decision Problem is NP-complete (opens in a new tab)

  4. Computational Complexity of Soundness Verification for Neural Networks

    … systems. Neural networks trained to solve NP-complete problems, in particular, are unlikely to be able to solve the problem exactly. However, a weaker soundness guarantee may be sufficient for some systems, e.g., that positive instances of the problem may be rejected but no negative …

    wustl Repository record for Computational Complexity of Soundness Verification for Neural Networks (opens in a new tab)

  5. Visualization of Ant Pheromone Based Path Following

    … as a demonstration of a heuristic approach to NP-complete problems and as an educational tool for demonstrating how ant colonies gather food. An interactive real time 3D visualization is built on top of the simulation. A graphical user interface layer allows user interaction with the simulation …

    tamu Repository record for Visualization of Ant Pheromone Based Path Following (opens in a new tab)

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

    vt Repository record for An Interactive Tutorial for NP-Completeness (opens in a new tab)

  7. Hamiltono ciklo ieškojimas kvantiniais skaičiavimais /

    … search problem is one of the most well-known problems in graph theory, and is relevant in many areas such as computer graphics, network routing, and many others. The Hamiltonian cycle problem belongs to the class of NP-complete problems, so that in the general case the solution of the problem …

    vilnius Repository record for Hamiltono ciklo ieškojimas kvantiniais skaičiavimais / (opens in a new tab)

  8. Topics in Graph Algorithms: Structural Results and Algorithmic Techniques, with Applications

    … the design of polynomial time algorithms for NP-complete problems in a way that guarantees some, often worst-case, satisfactory performance when compared to exact (optimal) solutions. We mainly study some emergent techniques that help to bridge the gap between computational intractability and …

    utk-theses Repository record for Topics in Graph Algorithms: Structural Results and Algorithmic Techniques, with Applications (opens in a new tab)

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

    rice Repository record for Branch decompositions and their applications (opens in a new tab)

  10. Automatic data layout for distributed memory machines

    … In the proposed framework, instances of NP-complete problems are solved during the construction of candidate layout search spaces and the final selection of candidate layouts from each search space. Rather than resorting to heuristics prematurely, the framework capitalizes on …

    rice Repository record for Automatic data layout for distributed memory machines (opens in a new tab)

  11. Dual-Based Local Search for Deterministic, Stochastic and Robust Variants of the Connected Facility Location Problem

    … propose the study of a family of network design problems that arise in a wide range of practical settings ranging from telecommunications to data management. We investigate the use of heuristic search procedures coupled with lower bounding mechanisms to obtain high quality solutions for …

    maryland Repository record for Dual-Based Local Search for Deterministic, Stochastic and Robust Variants of the Connected Facility Location Problem (opens in a new tab)

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

    rowan Repository record for Hybrid solvers for the Boolean Satisfiability problem: an exploration (opens in a new tab)

  13. Developing effcient simulators for cell machines

    … are suitable to tackle relevant real-life problems, usually involving NP-complete problems. Moreover, P systems are excellent tools to investigate on the computational complexity boundaries, in particular tackling the P versus NP problem. In this way, by studying how the ingredients …

    sevilla Repository record for Developing effcient simulators for cell machines (opens in a new tab)

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

    unt Repository record for Improved Approximation Algorithms for Geometric Packing Problems With Experimental Evaluation (opens in a new tab)

  15. Implementation of an efficient algorithm to detect maximal cliques in a conflict graph

    … graph model. However, detection of cliques is an NP-complete problem. Since NP-complete problems are not likely to be solvable in a reasonable time if the input is large, this paper limits the network input to six stations and fifteen transmissions. An algorithm is implemented in Pascal to detect …

    nps Repository record for Implementation of an efficient algorithm to detect maximal cliques in a conflict graph (opens in a new tab)

  16. Characterizing neighborhoods favorable to local search techniques

    NP-Complete problems are the most difficult problems to solve and polynomial time algorithms to solve these problems do not exist. One of the more powerful approaches for such problems are heuristic direct search techniques. For a given problem, a landscape is composed of (1) a solution space, (2) …

    texas Repository record for Characterizing neighborhoods favorable to local search techniques (opens in a new tab)

  17. Euristiniai algoritmai NP-pilniems uždaviniams spręsti ir jų realizacija GRIDui /

    … algorithms for GRID computing network to solve NP-complete problems. The problems of NP-complete set are not solved in polynomial time. To solve such problems, researchers have to use heuristic algorithms. Heuristic algorithms always give result in polynomial time, but it doesn’t mean that …

    vilnius Repository record for Euristiniai algoritmai NP-pilniems uždaviniams spręsti ir jų realizacija GRIDui / (opens in a new tab)

  18. An investigation into the structure of Chinese remainder representation

    … For a long time a number of CRR related problems have been recognized as being hard to implement efficiently. The lack of an efficient implementation for some of these problems has meant that CRR has only been able to be used to implement hardware solutions for very specific problems. The …

    jamescook Download PDF for An investigation into the structure of Chinese remainder representation (opens in a new tab)

  19. Relaxing synchronization in distributed simulated annealing

    … the solution to combinatorial optimization problems. Since simulated annealing is a general purpose method, it can be applied to the broad range of NP-complete problems such as the traveling salesman problem, graph theory, and cell placement with a careful control of the cooling schedule. …

    must-thes Repository record for Relaxing synchronization in distributed simulated annealing (opens in a new tab)

Page 1 of 5