Algorithmics for hard problems

This graduate course covers selected topics in Algorithm Theory that pertain in particular to the solution of problems where classically (worst-case) efficient algorithms are missing. Naturally, we concentrate on NP-hard problems. Pertinent topics are pseudo-polynomial algorithms, techniques related to backtracking, FPT algorithms, Linear Programming and Integer Programming.

Selected bibliography

Algorithmics for Hard Problems by Hromkovic

Computers and Intractability by Garey and Johnson

Fixed-Parameter Complexity by Downey and Fellows

Linear Programming by Vanderbei

Combinatorial optimization: algorithms and complexity by Papadimitriou and Steiglitz

Integer programming by Wosely