EP3360 Algorithms for Networks – Complexity and Approximations, 8 credits

Innehåll visas utifrån dina val

Om du inte hittar någon sida, schemahändelse eller nyhet på din kurswebb kan det bero på att du inte ser den kursomgången/gruppen inom kursen som innehållet tillhör.

Veta mer om din kurswebb

Din kurswebb är sidorna för en kurs du prenumererar på. Du väljer sedan vilka omgångar/grupper inom kursen du vill ha information från. Är du registrerad på en kursomgång sköts prenumeration och val av kursomgäng automatiskt åt dig. Vill du ändra något av detta gör du det under Mina inställningar.

När du är inloggad på din kurswebb ser du:
  • Kursöversikt, nyheter och schema med information som är filtrerat utifrån dina valda omgångar/grupper inom kursen
  • Allmänna sidor för hela kursen
  • Kurswikin som är sidor som alla, lärare och studenter, kan skapa och redigera
  • Sidor som hör till de omgångar/grupper inom kursen du valt eller som valts för dig

Log in to your group web

You are not logged in KTH, so we cannot customize the content.

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

No activity in the past month. Go to News feed to see older activity

Feedback News