Couverture de l'ensemble de fréquence bornée à cardinalité bornée: dureté de l'approximation

Considérez le problème de couverture de l'ensemble minimal avec les restrictions suivantes: chaque ensemble contient au plus éléments et chaque élément de l'univers se produit dans au plus ensembles.$k$$f$

• Exemple: le cas et est équivalent au problème de couverture minimale des sommets dans les graphiques avec un degré maximum 4.$k = 4$$f = 2$

Soit la plus grande valeur telle que trouver une approximation a du problème de couverture minimale avec les paramètres et soit NP-difficile.$a(k,f) > 1$$a(k,f)$$k$$f$

• Exemple: ( Berman & Karpinski 1999 ).$a(4,2) \ge 1.0128$

Question: Avons-nous une référence qui résume les bornes inférieures connues les plus fortes sur ? En particulier, je m'intéresse aux valeurs concrètes dans le cas où et sont petits mais .$a(k,f)$$k$$f$$f > 2$

Les versions restreintes du problème de couverture d'ensemble sont souvent pratiques dans les réductions; il y a généralement une certaine liberté dans le choix des valeurs de et , et des informations supplémentaires sur aideraient à choisir les bonnes valeurs qui fournissent les résultats de dureté les plus forts. Les références ici , ici et ici fournissent un point de départ, mais les informations sont quelque peu dépassées et fragmentaires. Je me demandais s'il y avait une source plus complète et à jour?$k$$f$$a(k,f)$

En utilisant la notation de paramètre plus courante au lieu de ( k , f ) , cela équivaut (et je pense plus communément appelé) au problème de couverture de sommet dans les hypergraphes k- uniformes de degré maximum Δ . Pour souligner, par souci de cohérence avec la littérature, j'utilise k où vous utilisez f et Δ où vous utilisez k .$(\Delta,k)$$(k,f)$$k$$\Delta$$k$$f$$\Delta$$k$

Pour toute constante , les résultats ignorant Δ incluent$\varepsilon > 0$$\Delta$

• $\sup_\Delta\{ a(\Delta,k) \}\leq k$
• $\sup_\Delta\{ a(\Delta,k) \}\geq k-1-\varepsilon$ (Dinur et al., 2004) , comme l'a noté Lev.
• Si la conjecture des jeux uniques est vraie, alors , ce qui est serré (Khot & Regev, 2008) .$\sup_\Delta \{a(\Delta,k)\} \geq k-\varepsilon$

Ignorant ,$k$

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

Le seul résultat que je connaisse qui combine les deux paramètres est

• kk$a(\Delta,k) \leq k - (1-o(1))\left(\frac{k(k-1)\ln\ln\Delta}{\ln(\Delta)}\right)$ pour fixe , ou croissant lentement avec (Halperin, 2002)$k$$k$$\Delta$

Il existe un lien entre ce problème et le problème de l'ensemble indépendant (faible), mais je ne sais pas exactement comment ils sont liés en termes d'approximation. Je recommanderais d'enquêter, peut-être en commençant ici: [PDF] .

En utilisant, comme dans la réponse de James King, la notation pour la meilleure approximation polynomiale temporelle possible de la couverture des sommets dans hypergraphes uniformes de degré au plus , nous avons égalementk $a(\Delta,k)$$k$$\Delta$

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

de l'algorithme d'approximation gourmand pour la couverture d'ensemble: la couverture des sommets dans les hypergraphes de degré au plus est la même que le problème de couverture d'ensemble avec des ensembles de taille au plus , pour lequel l'algorithme gourmand a un rapport d'approximation au plus , où est la fonction harmonique.Δ H Δ H n = 1 + 1 / deux + ... 1 / n ≤ ln n + O ( 1 $\Delta$$\Delta$$H_\Delta$$H_n = 1 + 1/2 + \ldots 1/n \leq \ln n + O(1)$

Dans cet article, je montre que

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

sauf , en modifiant les paramètres dans une réduction de Feige.$P=NP$

Juste au cas où vous ne l'auriez pas déjà trouvé; le résultat de dureté le plus récent pour la couverture de sommet de degré borné que j'ai trouvé dans une recherche récente est Chlebik & Chlebikova , par exemple environ 1,01-dureté dans les graphiques cubiques.

Cela ne répond pas tout à fait à votre question, mais cela peut peut-être aider - il existe un document [Dinur et al. 2004] qui couvre f> 2 (mais ne semble pas fixer k).