Przykłady trudnych instancji dla algorytmu Goemans i Williamson

Interesują mnie wyraźne przykłady wykresów, dla których zastosowanie algorytmu Goemansa i Williamsona do przybliżania maksymalnych cięć skutkuje współczynnikiem aproksymacji 0,878…

Algorytm do tworzenia takich instancji byłby idealny, wyraźne przykłady i referencje są zadowalające.

— mkatkov
źródło

Zastanawiam się, czy przeczytałeś ten artykuł eccc.uni-trier.de/report/2005/101

— Snowie

Odpowiedzi:

Myślę, że ten odnośnik dotyczy tego, o co pytasz:

N. Alon, B. Sudakov i U. Zwick. Konstruowanie najgorszych przypadków dla algorytmów aproksymacyjnych opartych na programowaniu półfinałowym . SIAM Journalon Discrete Mathematics, 15: 58–72, 2002.

Oto jego fragment (s. 60):

... przedstawiamy budowę wykresów, które pokazują, że lokalna analiza algorytmów MAX CUT [GW95] i [Zwi99] jest ścisła.

— Oleksandr Bondarenko
źródło

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.