Istnienie

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$

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.

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.