On probabilistic proof systems and hardness of approximation
Jonas Holmerin · 2002
In this thesis we study the approximability of combinatorial optimization problems whose decision versions are NP-complete. These problems cannot be solved exactly in polynomial time, unless P = NP. However, it may be possible to solve them approximately in polynomial time, i.e., there might exist a polynomial time algorithm which produces a solution whose value is always close to the optimum. An important