Angenommen, ich habe einen 2-Approximations-Algorithmus für ein bestimmtes Problem gefunden und möchte zeigen, dass die Analyse eng ist.
Muss ich jetzt ein Beispiel für die generische Größe oder reicht es aus zu zeigen, dass ich ein Beispiel für die Größe für das der Algorithmus ergibt ?
Das hängt von Ihrer Definition des Approximationsverhältnisses ab. Normalerweise wird das Approximationsverhältnis als das schlechteste Verhältnis zwischen der optimalen Lösung und der von Ihrem Algorithmus erzeugten definiert. Wenn dies der Fall ist, müssen Sie nur ein schlechtes Beispiel finden, um zu zeigen, dass das Verhältnis eng ist.
Manchmal beweisen Sie jedoch etwas wie . Dies bedeutet, dass Ihr Approximationsverhältnis tatsächlich beträgt . Um zu zeigen, dass dies eng ist, benötigen Sie ein Beispiel für unendlich viele Größen (aber nicht unbedingt für eine generische Größe; vielleicht haben alle Ihre Beispiele eine gerade Größe).
Die meisten Probleme ermöglichen es Ihnen jedoch, ein kleines Beispiel in ein größeres zu "skalieren".