Je recherche des résultats de dureté sur la coloration des sommets des graphiques à degré borné. Étant donné un graphique , nous savons que pour tout ϵ > 0 , il est difficile d'approximer χ ( G ) dans un facteur de | V | 1 - ϵ sauf si NP = ZPP [ 1 ]. Mais que se passe-t-il si le degré maximal de...
L'analyse lissée a été appliquée à plusieurs reprises pour comprendre le temps d'exécution d'algorithmes exacts pour de nombreux problèmes comme la programmation linéaire et les k-means. Il existe des résultats assez généraux dans ce domaine, par exemple Heiko Röglin et Berthold Vöcking, Smoothed...
Je suis à la recherche d'une classe de complexité qui se rapporte à APX comme BPP se rapporte à P. J'ai déjà posé la même question ici , mais peut-être TCS serait un endroit plus fructueux pour les réponses. La raison de la question est que dans les problèmes pratiques, il faut souvent trouver des...
Les jeux à deux provers et à un tour (2P1R) sont un outil essentiel pour la dureté de l'approximation. Plus précisément, la répétition parallèle de jeux à un tour à deux prouveurs permet d'augmenter la taille d'un écart dans la version de décision d'un problème d'approximation. Voir le sondage de...
Que sait-on actuellement de l'approximation du problème du genre? Une recherche préliminaire m'indique qu'une approximation à facteur constant est triviale pour des graphes suffisamment denses, et un algorithme d'approximation a été exclu. Ces informations sont-elles à jour ou existe-t-il de...
Pour un graphe donné , le problème du séparateur demande s'il existe un ensemble de sommets ou d'arêtes de petite cardinalité (ou poids) dont la suppression divise G en deux graphes disjoints de tailles approximativement égales. C'est ce qu'on appelle le problème du séparateur de sommets lorsque...
Je n'ai pas pu trouver dans la littérature une caractérisation précise de la disparition de l'écart de dualité SDP. Ou, quand la "forte dualité" tient-elle? Par exemple, quand on va et vient entre le Lasserre et le SOS SDP, on a en principe un écart de dualité. Cependant, d'une manière ou d'une...
J'ai entendu parler d'un résultat de coloration approximative du graphique, mais je ne trouve pas la source. Le résultat est: Pour chaque constante il existe un suffisamment grand pour que la coloration d'un graphique colorable avec des couleurs soit NP-difficile.hhhkkkkkkh khkhk Quelqu'un...
Est-il difficile d'approcher le nombre chromatique fractionnaire sur des graphiques de degrés
Considérez le problème de l'ensemble dominant dans les graphiques généraux, et soit le nombre de sommets dans un graphique. Un algorithme d'approximation gourmand donne une garantie d'approximation du facteur 1 + log n , c'est-à-dire qu'il est possible de trouver en temps polynomial une solution S...
Beaucoup ici sont probablement au courant de la baisse super-linéaire limite récente pour Alon -nets dans un cadre géométrique naturel [PDF] . Je voudrais savoir ce que, le cas échéant, une telle borne inférieure implique au sujet de l'approximation des problèmes de jeu de couverture / jeu de...
Soit une famille de sous-ensembles d'éléments d'un univers fini d'objets. Une famille de sous-ensembles d'éléments de , avec , est un - ensemble de frappes de si pour chaque il existe au moins un ensemble tel que .FFFdddUUUHHHkkkUUU1≤k<d1≤k<d1 \le k < d(k,d)(k,d)(k,d)FFFV∈FV∈FV \in FW∈HW∈HW...
Dans le problème Max-Cut , on cherche un sous-ensemble S de sommets d'un graphe simple non orienté donné tel que le nombre d'arêtes entre S et le complément de S soit le plus grand possible. Max-Cut est APX-complet sur les graphes à degrés bornés [PY91], et en fait APX-complet sur les graphes...
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...
Dans le problème des cliques plantées, il faut récupérer une -clique plantée dans un graphe aléatoire Erdos-Renyi G ( n , p ) . Cela a surtout été examiné pour p = 1kkkG ( n , p )G(n,p)G(n,p) , auquel cas il est connu pour être soluble dans le temps polynomial sik>√p = 12p=12p=\frac{1}{2} et...
Je me demande si le problème suivant a un nom ou des résultats qui y sont liés. G=(V,w)G=(V,w)G = (V,w)w(u,v)w(u,v)w(u,v)uuuvvvu,v∈Vu,v∈Vu,v \in Vw(u,v)∈[−1,1]w(u,v)∈[−1,1]w(u,v) \in [-1,1]maxS⊆V∑(u,v):u∈S or v∈Sw(u,v)maxS⊆V∑(u,v):u∈S or v∈Sw(u,v)\max_{S \subseteq V} \sum_{(u,v) : u \in S\...
Considérons le problème classique # P-complet # 3SAT, c'est-à-dire de compter le nombre d'évaluations pour rendre un 3CNF avec variables satisfaisable. Je m'intéresse à l' approximabilité additive . De toute évidence, il existe un algorithme trivial pour obtenir une erreur de , mais si , est-il...
J'étudie la Conjecture Unique Games et la fameuse réduction à Max-Cut de Khot et al. À partir de leur article et ailleurs sur Internet, la plupart des auteurs utilisent (ce qui pour moi est) une équivalence implicite entre la réduction MAX-CUT et la construction de tests particuliers pour les codes...