Istnienie

10

Rozważ problem z zestawem dominującym na ogólnych wykresach i niech będzie liczbą wierzchołków na wykresie. Chciwy algorytm aproksymacji daje gwarancję aproksymacji współczynnika , tzn. Możliwe jest znalezienie w czasie wielomianowym rozwiązania takiego, że , gdzie jest rozmiarem minimalnego zestawu dominującego. Istnieją ograniczenia wskazujące, że nie możemy poprawić zależności od dużo http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf . $n$ $1 + \log n$ $S$ $|S| \leq (1 + \log n) opt$ $opt$ $\log n$

Moje pytanie: czy istnieje algorytm aproksymacyjny, który ma gwarancję zamiast ? Na wykresach, gdzie jest bardzo duże w stosunku do optymalnego, przybliżenie współczynnika byłoby znacznie gorsze niż przybliżenie współczynnika . Czy coś takiego jest znane, czy istnieją powody, dla których to nie może istnieć? Jestem zadowolony z dowolnego algorytmu wielomianowego, który tworzy rozwiązanie takie jak dla pewnej stałej . $opt$ $n$ $n$ $\log n$ $\log opt$ $S$ $|S| \in O(opt^c)$ $c$

cc.complexity-theory approximation-algorithms approximation-hardness

— Bart Jansen
źródło

14

Myślę, że jest nadal otwarty, jeśli zestaw dominujący lub zestaw uderzeń ma przybliżenie af (OPT) dla niektórych (nietrywialnych) funkcji f. Na to pytanie powinno być bardzo trudne (i możliwe głębokie) pytanie. Uważam to za najbardziej ekscytujące pytanie w sparametryzowanym przybliżeniu (wraz z analogicznym pytaniem dla Clique). Możesz rzucić okiem na moją ankietę [1], która to omawia. Należy zauważyć, że w najnowszym artykule [2] wykazano, że „satysfakcjonowanie obwodu monotonicznego dla obwodów wątku 2”, który jest bardziej ogólny niż zestaw dominujący, nie ma aproksymacji f (OPT) dla żadnego f.

[1] D. Marks. Sparametryzowane algorytmy złożoności i aproksymacji. The Computer Journal, 51 (1): 60–78, 2008.

[2] D. Marks. Całkowicie niedopuszczalne problemy ze parametryzacją monotonu i antymonotonu. W postępowaniu z 25. dorocznej konferencji IEEE na temat złożoności obliczeniowej, Cambridge, Massachusetts, 181–187, 2010.

— Daniel Marks
źródło

Dzięki za referencje! To ładnie odpowiada na moje pytanie.

— Bart Jansen

Interesujące może być również przyjrzenie się poniższej notatce Nelsona, która pokazuje, że nie można uzyskać dobrych stosunków zależnych tylko od liczby zestawów. eccc.hpi-web.de/eccc-reports/2007/TR07-105/revisn01.pdf

— Chandra Chekuri

2

To powinien być komentarz, ponieważ nie odpowiada bezpośrednio na twoje pytanie, ale powiązane pytanie. Być może podobna sztuczka z [1] da ci odpowiedź.

W [1] udowodniono:

$G=(V,E)$ $k$ $k$ $G$ $g(k)$ $g(k)$ $k$ $G$ $k$

$g(k)$

[1] Rodney G. Downey, Michael R. Fellows, Catherine McCartin i Frances Rosamond. „Sparametryzowane przybliżenie problemów z zestawem dominującym”. Information Processing Letters, tom 109, wydanie 1, grudzień 2008.

— Ruub
źródło

1

Sztuczka w [1] opiera się na fakcie, że Niezależny Zestaw Dominujący jako problem maksymalizacji nie jest monotonowy: podzbiór wykonalnego rozwiązania niekoniecznie jest wykonalnym rozwiązaniem (co zwykle ma miejsce w przypadku problemów maksymalizacyjnych mających znaczące przybliżenia). Dlatego bardzo możliwe jest, że każde możliwe rozwiązanie ma ten sam rozmiar, co czyni przybliżenie nieistotnym.

— Daniel Marx