Till KTH:s startsida Till KTH:s startsida

EP3360 Algorithms for Networks – Complexity and Approximations, 8 credits

Logga in till din gruppwebb

Du är inte inloggad på KTH så innehållet är inte anpassat efter dina val.

Gruppwebben som samarbetsyta stängs 31 december 2026. Du som administratör behöver nu exportera gruppens innehåll och/eller radera gruppen.

Observera: Från och med den 1 oktober 2026 kommer delar av gruppwebben som inte längre används, successivt att stängas ned, exempelvis gruppwebbar som redan har flyttats eller varit inaktiva under en längre tid.

Mer information hittar du i nyheten: Gruppwebben och Social stänger hösten 2026. Stöd och instruktioner för hur du exporterar en gruppwebb finns i: Gruppwebben som samarbetsyta stängs hösten 2026.

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
Anmäl missbruk

Administratörer