Relation entre paramètre fixe et algorithme d'approximation

Les paramètres fixes et l'approximation sont des approches totalement différentes pour résoudre des problèmes difficiles. Ils ont une motivation différente. L'approximation recherche un résultat plus rapide avec une solution approximative. Le paramètre fixe recherche une solution exacte avec une complexité temporelle en termes d'exponentielle ou une fonction de k et une fonction polynomiale de n où n est la taille d'entrée et k est le paramètre. Exemple $2^kn^3$ .

Maintenant, ma question, existe-t-il un résultat de limite supérieure ou inférieure basé sur la relation entre le paramètre fixe et les approches d'approximation ou ils n'ont totalement aucune relation. Par exemple, pour un problème, est dit difficile pour certains n'a rien à voir avec l'algorithme d'approximation c ou PTAS. veuillez fournir quelques références $P$ $W[i]$ $i>0$

cc.complexity-theory reference-request approximation-algorithms fixed-parameter-tractable Prabu
la source

Liés, éventuellement en double?: Cstheory.stackexchange.com/questions/4906/…

Suresh Venkat

@suresh venkat Cette question concerne la différence de compréhension des paramètres NP-complets et fixes. lorsque nous parlons uniquement de dureté NP, alors l'ensemble indépendant et la couverture des sommets sont littéralement les mêmes, mais lorsque nous parlons en termes de paramètre fixe, ils ont une énorme différence. la couverture des sommets a un bon fpt alors que l'ensemble indépendant est dur [1]

Prabu

mais ici je cherche une relation entre approximation et paramètre fixe.

Prabu

Je pense qu'il n'y a pas de relation réelle entre eux, mais en utilisant un paramètre fixe, nous pouvons avoir une bonne approximation, par exemple dans le casier bin (planification makespan), vous pouvez voir cette relation, ou par exemple dans les graphiques Treewidth bornés, nous avons des approximations sur certains problèmes .

Saeed

Réponses:

Il existe plusieurs connexions entre la complexité paramétrée et les algorithmes d'approximation.

Considérons d'abord la soi-disant paramétrisation standard d'un problème. Ici, le paramètre est ce que vous optimiseriez dans la version d'optimisation du problème (la taille de la couverture de sommet pour le problème de couverture de sommet, la largeur de la décomposition de l'arbre pour le problème de la largeur d'arbre, etc.). Examinons concrètement Vertex Cover. Tout noyau avec un nombre linéaire de sommets pour Vertex Cover implique un algorithme d'approximation à temps polynomial à facteur constant: dans la solution approximative, placez tous les sommets qui ont été forcés dans la solution par l'algorithme de noyauisation, et tous les sommets de l'instance noyauée . En revanche, des bornes inférieures sur le facteur d'approximation impliquent des bornes inférieures sur la taille d'un noyau. Par exemple, sous la Conjecture des jeux uniques, Khot et Regev (JCSS 2008)exclure les algorithmes d'approximation pour Vertex Cover avec un rapport de tout , ce qui exclut un noyau pour Vertex Cover avec au plus sommets, , également. $c<2$ $ck$ $c<2$

EDIT: L'argumentation pour la limite inférieure du noyau dans le paragraphe précédent est très informelle, et à ma connaissance, il est ouvert de savoir si de telles limites inférieures sur la taille du noyau peuvent être prouvées, même pour Vertex Cover. Comme le souligne @Falk dans les commentaires, l'argument est valable pour la plupart (tous?) Des noyaux connus. Cependant, je ne vois pas comment on pourrait exclure l'existence d'algorithmes de kernelization où une solution réalisable de l'instance kernelized a un rapport d'approximation différent de la solution correspondante dans l'instance initiale.

Ensuite, il y a la question du PTAS par rapport au FPTAS. Si nous voulons trouver une solution dans optimale, nous pouvons paramétrer par . Ensuite, un PTAS correspond à un algorithme XP dans le paramétrage, tandis qu'un FPTAS correspond à un algorithme FPT. Pour une approximation de la borne inférieure, nous ne pouvons pas nous attendre à un EPTAS pour tout problème dont le paramétrage standard est W [1] -hard: l'exécution de l'EPTAS avec résoudrait le problème exactement en temps FPT. $(1+\epsilon)$ $1/\epsilon$ $\epsilon=1/(k+1)$

Enfin, un algorithme d'approximation FPT est un algorithme avec un temps d'exécution FPT et un rapport d'approximation qui peut dépendre du paramètre. Par exemple, le paramétrage standard du problème Cliquewidth a un algorithme d'approximation FPT avec un rapport d'approximation (Oum, WG 2005) , tandis que le paramétrage standard de Independent Dominating Set n'a pas d'algorithme d'approximation FPT avec rapport de performance pour toute fonction calculable , sauf si FPT = W [2] (Downey et al., IWPEC 2006) . Voir (Marx, The Computer Journal 2008) $(2^{3k+2}-1)/k$ $g(k)$ $g$ pour une enquête sur l'approximation FPT.

Serge Gaspers
la source

@Gasper Pouvez-vous voir la question "Trouver un sous-tournoi acyclique maximum compte tenu de deux sous-tournois acycliques". J'ai toujours un doute avec ma réponse. Comme vous avez travaillé avec un problème connexe, vous pouvez m'aider

Prabu

Le premier paragraphe de la réponse de Serge est-il correct? La borne inférieure sur l'approximation donne-t-elle une borne inférieure sur la taille du noyau? La déclaration similaire est dans le livre de Niedermeier, mais cette déclaration est-elle correcte?

XXYYXX

@XXYYXX: Dans la réponse de Serge, il a écrit "Tout noyau avec un nombre linéaire de sommets pour Vertex Cover implique un algorithme d'approximation à temps polynomial à facteur constant" avec une preuve courte. Plus précisément, son argument montre s'il existe un noyau avec ck sommets pour une constante c, alors il existe un algorithme d'approximation facteur-c. La contraposition est la suivante: si aucun algorithme d'approximation du facteur c n'existe, alors aucun noyau avec des sommets ck n'existe.

Yoshio Okamoto

@Prabu: J'ai commenté votre réponse à l'autre question. @Yoshio: Merci d'avoir répondu à la question de @ XXYYXX.

Serge Gaspers

En fait, pour probablement toutes les kernelizations connues, l'argument est valable. Cependant, je ne vois aucune raison pour laquelle il ne devrait pas y en avoir un qui, par exemple, se réduit d'abord à un autre problème, s'y noyauise, puis se ramène à Vertex Cover, de sorte que l'instance résultante n'a aucune correspondance de vertex avec la première. Il me semble donc que la seule chose que nous pouvons vraiment montrer est que les noyaux qui sont des sous-graphes ne seront probablement pas inférieurs à 2k.

Falk Hüffner

$FPTAS$ $PFPT$

$Q=(I_Q, S_Q, f_Q, opt_Q)$ $NP$ $Q$ $FPTAS$ $Q$ $PFPT$

$PFPT$

$NP$ $Q$ $PFPT$ $O(|x|^{O(1)}k^{O(1)})$ $|x|$ $x$

Une autre caractérisation pour deux classes d'approximation est proposée dans [2, Theorem 6.5].

Un problème est

$PTAS$ $ptas^{\infty}$ $XP^w$

$FPTAS$ $fptas^{\infty}$ $PFPT^w$

$(f)ptas^{\infty}$ $(XP)PFPT^w$ $\frac{1}{\epsilon}$

Schémas d'approximation du temps polynomial et complexité paramétrée . J. Chen et al. / Mathématiques appliquées discrètes 155 (2007) 180 - 193.
Structure de l'approximation polynomiale-temps . EJ van Leeuwen et al. Rapport technique UU-CS-2009-034, décembre 2009.

Oleksandr Bondarenko
la source