Przybliżalność problemu rodzaju

11

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ϵ


źródło

Odpowiedzi:

8

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.ε>0O(nε)

  • ngmax{4g,g+4n}

  • O(n)

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

Jeffε
źródło
2
O(nε)O(nε)
Tak, masz rację. Zaktualizowałem swoją odpowiedź w świetle twojej.
Jeffε
5

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(n1ε)Ggenus(G)ggenus(G)g+1gnGkN=nkGGgenus(G)Nggenus(G)N(g+1)genus(G)N=(Nn)k/k+1=|V(G)|k/k+1=|V(G)|1εε=1/(k+1)N(g+1)Ngg+1g

Yury
źródło