Seminars on Theoretical Computer Science

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 course web

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

The course in 2018 will focus on efficient approximability of NP-hard optimization problems.

There are many optimization problems, including Maximum Clique, Max Cut, Vertex Cover, TSP, etc such that finding the optimal solution is NP hard.  We will study the existence of efficient (polynomial time) algorithms which are approximation algorithms in the sense that for any input they give an answer that is within a factor C of optimal.  Here the quantity C might be a fixed constant or a function depending on input size.

Results in the area come in the form of positive results and hardness results.  A basic positive result is simply and algorithm together with an analysis that it is efficient and that it returns a solution of the required quality.  Hardness results are usually in the form of reductions using similar ideas to standard NP-completeness reductions.

The course will cover many methods for designing algorithms, including combinatorial techniques and approaches based on relaxations to linear or semidefinite programming.  An important technique is also to use randomness.

An important starting point for hardness results is thinking about very efficient proofs for general NP-statements.  In particular we will study probabilistically checkable proofs and we will discuss and use, (but probably not fully prove) the PCP-theorem.

Teachers

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

Feedback News