Vorlesung vom 22.03.2013

Initiates file downloadSlides

Slides for the

Initiates file download"Excursion NP-Completeness"

 

Summary

In this lecture we further examined the properties of constraint satisfaction problems. General CSPs are NP-complete which leads to an exponential runtime of solver algorithms. We discussed different strategies to deal with the NP-completeness or NP-hardness of practical problems:

  • Restrict the problem to a special case, for which a polynomial time algorithm is known.

  • Run tests to find out, whether the practical problem instances are easy enough to be solved with standard solvers.

  • Implement a heuristic solver and obtain approximate solutions.

An example for 1. is the X-Y-TSP, a special case of the Euclidean TSP, where the locations are aligned at the x- and y-axis of an orthogonal coordinate system. A deterministic algorithm was found in 2012 after more than 30 years of research:

http://www.alphagalileo.org/ViewItem.aspx?ItemId=124002&CultureCode=en http://www.scienceomega.com/article/595/making-life-easier-for-travelling-salespeople