Class Description

Course_ID: MYE055

Weekly Hours: 5

Semester: >=6

ECTS Credits: 5

Course Homepage: http://www.cse.uoi.gr/~cnomikos/courses/approx/approx-main.htm

Description: Optimization problems. Intractable computational problems and polynomial time approximation algorithms. Approximation ratio and asymptotic approximation ratio. Polynomial time approximation schemes. Techniques for designing approximation algorithms: greedy algorithms, local search, layering. Approximation algorithms for the problems VERTEX COVER, SET COVER, STEINER TREE, METRIC-TSP, k-CENTER, STRIP PACKING, MINIMUM MAKESPAN SCHEDULING, EDGE COLORING, MAXIMUM CUT, MAXIMUM SATISFIABILITY. A polynomial time approximation scheme for KNAPSACK.  An asymptotic polynomial time approximation scheme for BIN PACKING. Approximation algorithms based on Linear Programming. Reductions that preserve approximation ratio. Non-approximability.