EP3360 Algorithms for Networks – Complexity and Approximations, 8 credits

We plan the next course round for P2 2019.

The course covers the fundamentals of complexity theory and algorithm design with applications in networked system optimization. The course is intended for PhD students who perform research in the ICT area, and it prepares the students to use rigorous methods for proving the complexity of optimization problems and for designing approximation algorithms with provable worst case performance bounds for computationally intractable problems.

Learning outcomes

After the course the students should be able to:

• Correctly define computational complexity classes and analyze the complexity of algorithms;
• Discuss basic problems in areas of graph theory, sets and partitions, storage and scheduling;
• Formulate network design problems as decision or discrete optimization problems;
• Present procedures of proving NP-completeness and NP-hardness, and be able to provide proofs for basic examples;
• Use approximation algorithms to cope with NP-hard problems.

Course main content 

1. Problems, algorithms and complexity, polynomial time, NP-complete and NP-hard problems
2. Examples of polynomial time problems on graphs, greedy algorithms, networking examples
3. Famous NP-complete problems, proof of NP completeness, problems beyond NP,
4. Polynomial-time reduction, NP-hard problems, networking examples
5. Approximation methods and algorithms – greedy strategy, restriction, partition
6. Approximation methods and algorithms – relaxation, primal-dual schemes and local ratio
7. Proof of complexity and algorithm design for networking problems based on recent literature