Przybliżalność problemu rodzaju

Co obecnie wiadomo na temat zbliżenia problemu rodzaju? Wstępne wyszukiwanie mówi mi, że stałe przybliżenie współczynnika jest trywialne dla wystarczająco gęstych wykresów, a algorytm aproksymacji został wykluczony. Czy te informacje są aktualne, czy są znane lepsze granice?$n^\epsilon$

Najlepsze opublikowane wyniki zostały opublikowane w artykule z 1997 r. Autorstwa Jianera Chena, Saroji P. Kanchi i Arkadego Kanevsky'ego.

• Dla każdego ustalonego obliczenie rodzaju wykresu z błędem addytywnym O ( n ε ) jest trudne.$\varepsilon>0$$O(n^\varepsilon)$

• $n$$g$$\max\{4g, g+4n\}$

• $O(\sqrt{n})$

Pytanie, czy istnieje skuteczny algorytm aproksymacji o stałym współczynniku.

Chciałem dodać do wyczerpującej odpowiedzi Jɛ ff E, że zgodnie z moją najlepszą wiedzą nie ma dolnych granic współczynnika przybliżenia dla tego problemu. O ile nam wiadomo, może istnieć algorytm aproksymacyjny, który zawsze zapewnia stałe przybliżenie współczynnika (nawet jeśli rodzaj jest bardzo mały).

$O(n^{1-\varepsilon})$$G$$\mathrm{genus}(G) \leq g^*$$\mathrm{genus}(G) \geq g^*+1$$g^*$$n$$G$$k$$N = n^k$$G$$G'$$\mathrm{genus}(G') \leq N g^*$$\mathrm{genus}(G') \geq N(g^*+1)$$\mathrm{genus}(G')$$N = (Nn)^{k/{k+1}} = |V(G')|^{k/{k+1}} = |V(G')|^{1-\varepsilon}$$\varepsilon = 1/(k+1)$$N(g^*+1)$$Ng^*$$g^*+1$$g^*$