Que signifie le 2 dans un algorithme à 2 approximations?

Est-ce que le 2 dans un algorithme à 2 approximations signifie que la solution est dans 2 * OPT ou OPT / 2?

algorithms algorithm-analysis np approximation polynomial-time Hrishikesh
la source

Réponses:

En règle générale, nous utilisons pour les problèmes de maximisation et pour les problèmes de minimisation, où est la garantie d'approximation. Ainsi, un algorithme d'approximation renvoie une solution dont le coût est au maximum deux fois optimal. Mais comme toujours, pour être absolument sûr, revenez aux définitions du texte que vous lisez (si une définition n'est pas disponible, supposez-le). $\alpha < 1$ $\alpha > 1$ $\alpha$ $2$

Juho
la source

Référence

Timmmm

J'ai certainement vu

α > 1

$\alpha > 1$ utilisé pour des problèmes de maximisation, bien que personnellement je préfère

α < 1

$\alpha < 1$ .

Yuval Filmus