Najcięższy plansza podrzędna

9

Rozważ następujący problem.

Biorąc pod uwagę: Pełny wykres z rzeczywistymi nieujemnymi wagami na krawędziach.

Zadanie: znajdź płaski wykres podrzędny o maksymalnej masie. („Maksimum” wśród wszystkich możliwych płaskich wykresów podrzędnych.)

Uwaga: Podgraf maksymalnej wagi będzie triangulacją; jeśli cały wykres jest na wierzchołkach, będzie miał krawędzi.nm=3)n-6

Pytanie: Jaki jest najlepszy dostępny algorytm dla tego problemu? Jaka jest złożoność czasu?

Helen F.
źródło

Odpowiedzi:

6

Jest to trudne dla NP nawet dla ważonych kompletnych wykresów. Aby uzyskać prosty algorytm, możesz obliczyć drzewo opinające o maksymalnej masie: zaneguj wagi krawędzi i uruchom algorytm Kruskala. Daje to współczynnik wydajności wynoszący 1/3 (drzewo opinające man-1 krawędzie i, jak zauważysz, maksymalny płaski wykres podrzędny może zawierać co najwyżej 3)n-6krawędzie). O ile mi wiadomo, algorytm w [1], który ma współczynnik wydajności co najmniej 25/72, a co najwyżej 5/12, nie został znacznie ulepszony (ale zobacz, o czym wspominają nowsze artykuły).

Dla kompletnych wykresów, których wagi krawędzi są zgodne z nierównością trójkąta, współczynnik wydajności algorytmu w [1] wynosi co najmniej 3/8. Myślę, że algorytm jest raczej zaangażowany i można go uruchomićO(m3)/2)nlog6n)czas na ogólnych wykresach. Istnieje kilka prostszych wariantów, które autorzy przedstawiają również z różnymi współczynnikami wydajności i prawdopodobnie lepszymi czasami działania.


[1] Calinescu, G., Fernandes, CG, Karloff, H., & Zelikovsky, A. (2003). Nowy algorytm aproksymacyjny do wyszukiwania ciężkich podgrup płaskich. Al Algorytmica, 36 (2), 179-205.

Juho
źródło