Superpolynomielle Zeitnäherungsalgorithmen für Optimierungsprobleme

Dies ist durch meine vorherige Frage, Superpolynom-Zeitnäherungsalgorithmen für MAX-3SAT, motiviert . Für viele Optimierungsprobleme haben wir für jedes eine ungefähre Untergrenze Annahme einer weithin angenommenen komplexitätstheoretischen Vermutung. Mit anderen Worten, es gibt keinen Polynomzeitalgorithmus für solche Optimierungsprobleme mit einem Approximationsverhältnis, das besser ist als einige (unterschiedliches Verhältnis für jedes Problem).α $\alpha$$\alpha$$\alpha$

Gibt es Optimierungsprobleme, bei denen wir ein besseres Approximationsverhältnis als erzielen können, wenn wir superpolynomielle Zeitalgorithmen zulassen? Können wir mit quasi-polynomiellen Zeitalgorithmen ( ) oder sogar mit subexponentiellen Zeitalgorithmen ( ) bessere Approximationsverhältnisse erzielen ?n O ( log n ) 2 o ( n $\alpha$$n^{O(\log n)}$$2^{o(n)}$

Ich würde mich über eine Übersicht über solche Ergebnisse freuen.

Ein Beispiel ist Maximum Independent Set . Es ist NP-schwer, das Problem mit dem Verhältnis zu approximieren (Zuckerman, 2007) . Allerdings Bourgeois et al. (2011) geben einen einfachen -Annäherungsalgorithmus mit der Laufzeit . Hier bezeichnet die Anzahl der Eckpunkte des Eingabegraphen und die -Notation verbirgt Polynomfaktoren.$n^{1-\epsilon}$ O * ( 2 $n^{1/2}$nO$O^*(2^{\sqrt{n} \log n})$$n$$O^*$

Ein weiteres Beispiel ist das Bandbreitenproblem . Dunagan & Vempala (2001) entwerfen einen Algorithmus mit dem Approximationsverhältnis und der Laufzeit . Meines Wissens hat die bekannteste polynomielle Zeitnäherung das Näherungsverhältnis (Lee, 2009) ; Es ist jedoch keine Untergrenze von für das beste Approximationsverhältnis bekannt, das in der Polynomzeit erreichbar ist.O ( n log n ) O ( log 3 n ( log log n ) 1 / 4 ) ω ( $O(\log^3 n)$$O(n^{\log n})$$O(\log^3 n (\log \log n)^{1/4})$ $\omega(\sqrt{\log n / \log \log n})$