Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Introduction

Due to the fact that no NP-complete problem can be solved in polynomial time (unless P=NP), many approximability results (both positive and negative) of NP-hard optimization problems have appeared in the technical literature. In this compendium, we collect a large number of these results.

In the following we refer to standard complexity classes (see [277]). We recall that a function t(n) is `quasi-polynomial' if a constant c exists such that $t(n) \leq n^{\log^cn}$ and we denote by QP, QNP, and QR the analogues of the usual complexity classes in the quasi-polynomial time domain.