Книга: Nitish Sabharwal and Harshit Sharma «Approximate Algorithms for some NP-hard problems»
|
Производитель: "LAP Lambert Academic Publishing" In this era of information technology, many decisions are made rapidly by computers in various industries to achieve some best possible goal or objective, from routing vehicles, to deciding inventory, model networks and for efficient data retrieval. For many such problems, we cannot conduct an exhaustive search of all the solutions to find the optimal solution in polynomial time, as they have an exponential population of possibilities. Such problems are referred to as NP-hard and we have focused on such type of problems in this monograph. We have proposed some interesting approximate algorithms and heuristics to solve the Traveling Salesman Problem and the Hamiltonian Cycle Problem and get good quality solutions. The computer simulations performed show the effectiveness of our algorithms. ISBN:9783659150920 Издательство: "LAP Lambert Academic Publishing" (2012)
ISBN: 9783659150920 |
См. также в других словарях:
Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… … Wikipedia
Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… … Wikipedia
2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… … Wikipedia
Numerical analysis — Babylonian clay tablet BC 7289 (c. 1800–1600 BC) with annotations. The approximation of the square root of 2 is four sexagesimal figures, which is about six decimal figures. 1 + 24/60 + 51/602 + 10/603 = 1.41421296...[1] Numerical analysis is the … Wikipedia
Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… … Wikipedia
Iterative method — In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination… … Wikipedia
