Advanced Algorithms
| Code | 3.4.3135.8 |
|---|---|
| Semester | 8th |
| Flow | L - Computer Software |
| Category | Obligatory by selection |
| Credits | 4 |
| Class Hours - Lab Hours | 3 - 0 |
| Lecturers | Dimitris Fotakis, Aris Pagourtzis |
| Links | Course's Website |
Description
Optimization problems, convexity and optimization. Linear programming, geometry, basic feasible solutions, Simplex, duality, complementary slackness conditions. Max flow, min cut, min cost flow. Randomized algorithms, max cut, Chernoff-Hoeffding bounds, applications to load balancing and random sampling. Approximation algorithms, basic techniques, LP-based approximation algorithms, randomized rounding, the primal-dual method, inapproximability, approximation preserving reductions. Online algorithms, paging, scheduling and load balancing problems, network design problems. Algorithmic game theory, Nash equilibrium, price of anarchy, congestion games, stable matchings, mechanism design.