1

NP Completeness

• Traveling Salesperson Problem (TSP):

– Given a weighted undirected graph G= (V, E), find a cycle

containing every vertex exactly once such that the sum of

weights of edges in the cycle is a minimum.

– A greedy algorithm does not work (see next slide).

– An exhaustive search will “work” but takes much too long for

even moderate values of n.

• Exhaustive search: Trying each permutation of the cities involves

testing (n - 1)! sequences.

– There is no known polynomial time algorithm that is

guaranteed to find the minimal cost tour.

– There are many polynomial time algorithms to generate

approximations to the optimal solution.

TSP & Greedy (Near Neighbour)

• Consider NN “solution” for rd100 taken from

TSPLIB:

Start here

TSPLIB: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

2

Practical vs. Impractical

• A simple characterization of algorithms:

– We will consider polynomial time algorithms to be

“practical” or efficient

• (even with large exponents)

– Algorithms that require exponential time (or worse)

are regarded as “impractical”.

The Question of Efficiency

• What do we do if we have a problem like TSP

that has no polynomial time solution?

If we could prove that no polynomial time algorithm

can be designed to solve the problem,

then we could go about looking for approximate

solutions or heuristics with knowing that no practical

algorithm exists to find the optimal solution.

– There is a set (class) of problems that require

exponential solutions and this can be proven.

– But there are many other problems (e.g. TSP) for

which such a proof is not known despite

considerable effort by researchers.

3

• So instead we must go for a lesser prize:

– We prove that the problem is “NP-hard”.

• That is: it is essentially equivalent to other problems for

which no known polynomial time solution exists.

• Such a proof does not show that a polynomial time

solution does not exist but only that thousands of other

experts have never found an efficient solution either.

– Why is this important?

• If you have an NP-hard problem you have two choices:

1.You can decide that all the experts have missed some

vital point and so you set about looking for a polynomial

time solution…

2.You decide that you are not likely to do better than the

experts and set about looking for an approximation or

heuristic algorithm that gives a reasonable solution.

Optimization vs. Decision Problems

• Optimization problems:

– Find a value, object or configuration that optimizes

some function.

• For example: in TSP we are looking for a least cost tour.

• Decision problems:

– The solution of a decision problem is “yes” or “no”.

– Some examples:

• Is a given number a prime number?

• In the TSP-D problem we are given a value Band we

want to know whether there is a tour with length < B.

–NP-completeness theory deals with decision

problems.D for Decision

**Unlock Document**

## More from OC17497

###### Assignment #3 This is the third assignment from winter 2010 term

Lecture Note

###### CS341 Lecture Notes - Greedy Algorithm, Gordon Gekko, Huffman Coding

Lecture Note

###### CS341 Lecture Notes - Dynamic Programming, Richard E. Bellman, Artery Recordings

Lecture Note

## Similar documents like this

###### Assignment #3 This is the third assignment from winter 2010 term

Lecture Note

###### Assignment #4 This is the forth assignment from winter 2010 term

Lecture Note

###### Assignment #5 This is the fifth assignment from winter 2010 term

Lecture Note

###### CS341 Lecture Notes - Biconnected Component, Two Trees Of Valinor, Computer Network

Lecture Note

###### CS341 Lecture Notes - Intel 80386, Precautionary Statement, Quicksort

Lecture Note

###### Assignment #1 This is the first assignment from winter 2010 term

Lecture Note

###### CS341 Lecture Notes - Closest Pair Of Points Problem, Euclidean Distance, Subroutine

Lecture Note

###### CS341 Lecture Notes - Greedy Algorithm, Gordon Gekko, Huffman Coding

Lecture Note

###### CS341 Lecture Notes - Dynamic Programming, Richard E. Bellman, Artery Recordings

Lecture Note

###### CS341 Lecture Notes - Merge Sort, Binary Search Algorithm, Dont

Lecture Note

###### CS341 Lecture Notes - Nsw Trainlink V Set, Correspondence Problem, Natural Number

Lecture Note

###### CS341 Lecture Notes - Merge Sort, Quicksort, Binary Search Algorithm

Lecture Note

###### Assignment #2 This is the second assignment from winter 2010 term

Lecture Note

###### CS341 Lecture Notes - Induced Subgraph, Adjacency Matrix, Tree Traversal

Lecture Note

###### CS 341 Chapter -: exercise5

Textbook Note