Inapproximabilité de la couverture définie: puis-je supposer que m = poly (n)?

J'essaie de montrer qu'un certain problème est inapproximable par une réduction de la couverture réglée. Ma réduction transforme une instance avec un ensemble au sol de taille et ensembles en une instance de mon problème où un certain paramètre est de taille . Je peux alors montrer qu'une instance de set cover où la taille de la couverture est s correspond à une instance de mon problème où la taille de la solution optimale est de (ou quelque chose comme ça), et vice versa. Je voudrais invoquer Raz-Safra pour conclure que mon problème est inapproximable jusqu'à un facteur de , pour une constante . Cela fonctionnerait bien si je pouvais supposer que $n$ $m$ $r$ $O(n+m)$ $2s$ $c \log{r}$ $c$ $m$ est borné par un polynôme fixe de . Est-ce que quelqu'un sait s'il est casher de supposer cela? Cela est certainement vrai pour la famille d'instances utilisées dans la preuve de dureté NP standard pour la couverture d'ensemble, mais je ne suis pas sûr que cela reste le cas pour le type de réductions de PCP utilisées par Raz et Safra. $n$

cc.complexity-theory approximation-hardness set-cover Edith Elkind
la source

Oui, le nombre d'ensembles m dans une instance de set-cover est polynomial dans le nombre d'éléments.

Soit dit en passant - les résultats de dureté les plus récents pour Set-Cover sont:

Avec Noga Alon et Muli Safra, nous avons montré comment utiliser le PCP Raz-Safra / Arora-Soudan pour obtenir une meilleure constante $c$ dans le facteur de dureté $c\log n$ .

http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest-full.ps
$(1-\epsilon)\ln n$ $NP\not\subseteq DTIME(n^{\log\log n})$

http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf
J'ai récemment publié une note sur la façon d'adapter la réduction de Feige à un résultat de dureté NP (c'est-à-dire un résultat basé sur ), en supposant une conjecture plausible sur les PCP (une conjecture que j'appelle "The Projection Games Conjecture" - une spécialisation du "Sliding Scale Conjecture" de 1993 aux jeux de projection). $P\neq NP$

http://eccc.hpi-web.de/report/2011/112/ (j'ai découvert plus tard que la réduction donne un compromis optimal entre et l'explosion de réduction). $\epsilon$

Dana Moshkovitz
la source

Quelle est l'hypothèse de séparation la plus faible qui produira toujours une dureté ?

(1 - ϵ) \log n

$(1-\epsilon)\log n$

Suresh Venkat du

Dana, merci pour ta réponse! Une question de suivi, si cela ne vous dérange pas: est-ce une question "stupide", c'est-à-dire, y a-t-il des considérations de haut niveau qui impliquent m = poly (n), ou est-ce le cas que l'on doit réellement connaître le Preuve de dureté Raz-Safra pour répondre à ma question?

Edith Elkind

@Suresh: Je suppose que vous voulez dire . L'hypothèse de Feige ( ) et mon hypothèse ("The Projection Games Conjecture") sont incomparables. Je crois que mon hypothèse serait prouvée dans un avenir prévisible.

(1 - ϵ) \ln n

$(1-\epsilon)\ln n$

N P ⊈ D T I M E (n^{\log \log n})

$NP\not\subseteq DTIME(n^{\log\log n})$

Dana Moshkovitz

@lostinjungle: Si m n'avait pas été polynomial en n, vous n'auriez pas pu considérer la réduction comme une "réduction poly-temps". La raison particulière pour laquelle un PCP Raz-Safra / Arora-Soudan donne m = poly (n) est qu'il y a un ensemble par variable / contrainte + PCP et leur affectation, ainsi que le nombre de variables et de contraintes, ainsi que le la taille de l'alphabet est polynomiale et le nombre de requêtes est constant.

Dana Moshkovitz du

@DanaMoshkovitz: Merci! Cependant, je ne suis pas sûr de comprendre votre première affirmation. Quel est le problème avec la réduction (hypothétique) suivante: je commence par une instance de (disons) Vertex Cover avec sommets et crée une instance de Set Cover avec sets et ground set de taille , où est la solution à ? Cela fonctionne certainement en poly-temps. Certes, je n'ai jamais vu une telle réduction, mais cela ne semble pas logiquement impossible. Ou ai-je tort? Bien sûr, ma question d'origine a déjà été répondue, alors n'hésitez pas à ignorer celle-ci. Je suis juste curieuse ...

k

$k$

m = k^{3}

$m = k^3$

n

$n$

n

$n$

n^{\log n} = m

$n^{\log n} = m$

Edith Elkind

Inapproximabilité de la couverture définie: puis-je supposer que m = poly (n)?

Réponses: