Du är inte inloggad på KTH så innehållet är inte anpassat efter dina val.
The course in 2020 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.