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?
11
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).
źródło