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


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.