Was bedeutet die 2 in einem 2-Approximationsalgorithmus?

Antworten:

10

Normalerweise verwenden wir für Maximierungsprobleme und für Minimierungsprobleme, wobei die Annäherungsgarantie ist. Ein Approximationsalgorithmus gibt also eine Lösung zurück, deren Kosten höchstens doppelt so hoch sind wie das Optimum. Aber wie immer, um absolut sicher zu sein, kehren Sie zu den Definitionen des Textes zurück, den Sie lesen (wenn eine Definition nicht verfügbar ist, nehmen Sie dies an).α<1α>1α2

Juho
quelle
Referenz
Timmmm
Ich habe definitiv gesehen, dass für Maximierungsprobleme verwendet wird, obwohl ich persönlich bevorzuge . α>1α<1
Yuval Filmus