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

26

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.kf

  • Exemple: le cas et est équivalent au problème de couverture minimale des sommets dans les graphiques avec un degré maximum 4.k=4f=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)>1a(k,f)kf

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)kff>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?kfa(k,f)

Jukka Suomela
la source
Merci pour les réponses fournies jusqu'ici! Commençons une prime et voyons si nous pouvons obtenir plus de participation. Par souci de concrétisation, je serai heureux d'attribuer la prime si quelqu'un donne un pointeur vers une borne inférieure non triviale sur a(3,3) .
Jukka Suomela
... et la prime est allée à la réponse qui a donné quelque chose qui était le plus proche d'une borne inférieure sur a(3,3) , mais pour des raisons d'équité, j'ai décidé d'accepter la réponse la plus complète. Merci à tous; il semble que le cas d' a(3,3) soit bien ouvert.
Jukka Suomela

Réponses:

15

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 .(Δ,k)(k,f)kΔkfΔk

Pour toute constante , les résultats ignorant Δ incluentε>0Δ

  • supΔ{a(Δ,k)}k
  • supΔ{a(Δ,k)}k1ε (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Δ{a(Δ,k)}kε

Ignorant ,k

  • supk{a(Δ,k)}Δ (trivial).
  • supk{a(4,k)}2ε (Holmerin, 2002)

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

  • kkΔa(Δ,k)k(1o(1))(k(k1)lnlnΔln(Δ)) pour fixe , ou croissant lentement avec (Halperin, 2002)kkΔ

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] .

James King
la source
Merci pour les pointeurs et excuses pour l'utilisation des paramètres quelque peu déroutants. (J'ai essayé d'être cohérent avec l'utilisation du paramètre dans la " couverture minimale de l'ensemble ", et j'ai décidé de suivre la notation utilisée dans le livre de Vazirani.)kkk
Jukka Suomela
12

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(Δ,k)kΔ

(1)a(Δ,k)lnΔ+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 )ΔΔHΔHn=1+1/2+1/nlnn+O(1)

Dans cet article, je montre que

(2)supk{a(Δ,k)}lnΔO(lnlnΔ)

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

Luca Trevisan
la source
7

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.

daveagp
la source
6

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).

Lev Reyzin
la source