Zakres ograniczonej liczności ograniczonej obejmuje: twardość aproksymacji

Rozważ problem minimalnego pokrycia zestawu z następującymi ograniczeniami: każdy zestaw zawiera co najwyżej $k$ elementów, a każdy element wszechświata występuje w co najwyżej zestawach $f$

• Na przykład: w przypadku $k = 4$ i $f = 2$ odpowiada minimalnej wierzchołek problemu pokrywy na wykresach z maksymalnym stopniem 4.

Niech $a(k,f) > 1$ będzie największą wartością, tak że znalezienie $a(k,f)$ aproksymacji minimalnego zestawu problemów obejmujących parametry $k$ i $f$ jest NP-trudne.

• Przykład: $a(4,2) \ge 1.0128$ ( Berman i Karpinski 1999 ).

Pytanie: Czy mamy odniesienie podsumowujące najsilniejsze znane dolne granice na $a(k,f)$ ? W szczególności interesują mnie konkretne wartości w przypadku, gdy oba $k$ i $f$ są małe, ale $f > 2$ .

Ograniczone wersje zestawu problemów z pokrywą są często wygodne w redukcji; zazwyczaj istnieje pewna swoboda w wyborze wartości $k$ i $f$ , a dalsze informacje na $a(k,f)$ pomogłyby wybrać odpowiednie wartości, które zapewniają najsilniejsze wyniki twardości. Odniesienia tutaj , tutaj i tutaj stanowią punkt wyjścia, ale informacje są nieco nieaktualne i fragmentaryczne. Zastanawiałem się, czy istnieje bardziej kompletne i aktualne źródło?

$(\Delta,k)$$(k,f)$$k$$\Delta$$k$$f$$\Delta$$k$

$\varepsilon > 0$$\Delta$

• $\sup_\Delta\{ a(\Delta,k) \}\leq k$
• $\sup_\Delta\{ a(\Delta,k) \}\geq k-1-\varepsilon$ (Dinur i in., 2004) , jak zauważył Lev.
• Jeśli hipoteza dotycząca unikalnych gier jest prawdziwa, to , co jest ścisłe (Khot i Regev, 2008) .$\sup_\Delta \{a(\Delta,k)\} \geq k-\varepsilon$

Ignorując ,$k$

• $\sup_k\{ a(\Delta,k) \}\leq \Delta$ (trywialny).
• $\sup_k\{ a(4,k) \}\geq 2-\varepsilon$ (Holmerin, 2002)

Jedyny znany mi wynik, który łączy te dwa parametry

• $a(\Delta,k) \leq k - (1-o(1))\left(\frac{k(k-1)\ln\ln\Delta}{\ln(\Delta)}\right)$ dla naprawiono lub rosnące powoli z (Halperin, 2002)$k$$k$$\Delta$

Istnieje związek między tym problemem a (słabym) zestawem niezależnym, ale nie jestem do końca pewien, w jaki sposób są one powiązane pod względem przybliżalności. Poleciłbym to zbadać, być może zaczynając tutaj: [PDF] .

Używając, jak w odpowiedzi Jamesa Kinga, zapisu dla najlepszego możliwego przybliżenia czasu wielomianowego pokrycia wierzchołka w -jednostkowych hipergraphach stopnia co najwyżej , mamy również$a(\Delta,k)$$k$$\Delta$

(1)$a(\Delta,k) \leq \ln \Delta + O(1)$

z algorytmu chciwego aproksymacji dla pokrycia zestawu: pokrycie wierzchołka w hiperrafiach stopnia co najwyżej jest takie samo jak problem zestawu pokrycia z zestawami wielkości co najwyżej , dla którego chciwy algorytm ma współczynnik przybliżenia co najwyżej , gdzie jest funkcją harmoniczną.$\Delta$$\Delta$$H_\Delta$$H_n = 1 + 1/2 + \ldots 1/n \leq \ln n + O(1)$

W tym artykule to pokazuję

(2)$\sup_k \{ a(\Delta ,k) \} \geq \ln \Delta - O(\ln\ln \Delta)$

chyba że , poprzez zmianę parametrów w redukcji Feige.$P=NP$

Na wypadek, gdybyś go jeszcze nie znalazł; najnowszy wynik twardości dla osłony wierzchołków ograniczonych, który znalazłem podczas ostatnich poszukiwań, to Chlebik i Chlebikova , np. około 1,01 twardości w grafach sześciennych.

To nie do końca odpowiada na twoje pytanie, ale być może może pomóc - jest artykuł [Dinur i in. 2004], który obejmuje f> 2 (ale wydaje się nie naprawiać k).