Slajdy z přednášky                                                                                                                         

Upozornění: slajdy obsahují základní definice, pseudokódy a teze probíraných technik. Ideální je dopisovat si do slajdů vlastní poznámky a komentáře z přednášky. Slajdy se nedají použít jako samostatná studijní literatura bez zhlédnutí přednášky resp. nastudování tematiky  z jiných zdrojů (viz např. následující seznam učebnic).

Literatura

• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011.
• V. Vazirani. Approximation algorithms. Springer, 2001.
• R. Motwani, P. Raghavan. Randomized algorithms. Cambridge University Press, 1995.
• J. Hromkovič. Algorithmics for hard problems :introduction to combinatorial optimization, randomization, approximation, and heuristics. Springer, 2001.
• T. Cormen, Ch. Leiserson, R. Rivest, C. Stein. Introduction to algorithms. 3rd edition. MIT Press, 2009.
• W. Cook. In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press, 2012.
• V. Chvátal. Linear programming. W.H. Freeman and Company, 1983.

Online zdroje

Lecture Notes

• Lecture Notes: David P. Williamson 1
• Lecture Notes: David P. Williamson 2
• The Primal-Dual Method. (by Eric Bauer and Martin Zinkevich)

Tools

• Tutorial for the Simplex Method
• Simplex Method Tool
• TSP Solver

Web pages

• A compendium of NP-optimization problems
• SAT competitions
• Traveling Salesman Problem

Presentations

• Heuristics for Efficient SAT Solving (ppt)

Příklady k procvičení

• Sada 1
• Sada 2
• Sada 3
• Sada 4
• a další příklady