Erreur liée à la limite d'un algorithme pour la couverture de sommet

Question

J'ai l'algorithme randomisé suivant pour le problème de la couverture de sommet. Laissez $ b_0 $ être le jeu de sortie:

• Fixez une certaine commande $ e_1, e_2 ,. . . , e_m $ sur tous les bords de l'EDGE SET E de G, et définissez $ B_0=EKTYSET $
. .
• Ajouter à $ B_0 $ Tous les sommets isolés, c'est-à-dire ceux sans bords incidents.
• pour chaque bord $ E $ in $ e_1, e_2 ,. . . , e_m $
  • si les deux points d'extrémité de $ E $ non contenus dans $ b_0 $ , alors
  • Retournez une pièce de monnaie juste décidant lequel des points de terminaison choisissez et ajoutez ce point d'extrémité à $ b_0 $ .
  . .

Comment puis-je prouver que, pour chaque constante $ C \ geq 1 $ , l'algorithme peut produire une $ b_0 $ avec $ | b_0 | \ ge c | opt | $ ?

Answer 1

correction d'un graphe star de $ C + 1 $ sommets. Un graphe Star est un sommet connecté à tous les autres sommets du graphique (un sommet universel appelé le centre), et tous les autres sommets sont paires non adjacents. Voici un exemple visuel. $ C $ est le centre de l'étoile.

Maintenant une solution optimale consiste à emballer le centre de l'étoile. La taille de cette solution est égale à 1. Pour chaque bord, supposons que notre algorithme emballe l'autre extrémité du bord (le sommet non universel), puis nous devons emballer tous les sommets du graphique à l'exception du centre et donc, nous Besoin d'emballer $ C $ C $ différents sommets. Au total, nous obtenons $ | b_0 |= C | opt | $ pour toute valeur arbitraire mais fixe de $ C $ .

---

note Une simple modification de l'algorithme donne un algorithme d'approximation derandomisé avec une taille de réponse au plus deux fois plus grand que l'optimum. Il va comme suit: Si les deux points d'extrémité du bord ne sont pas dans $ b_0 $ , puis ajoutez points de terminaison $ b_0 $ et itérer.

La raison pour laquelle cette fonction est simple. Les bords, qui obtiennent leurs points d'extrémité ajoutés pour une correspondance maximale et, par conséquent, nous ajoutons deux fois le nombre de sommets dans une correspondance maximale à la couverture. Notez que la taille d'une correspondance dans un graphique est une liaison inférieure de la taille d'une couverture de sommet minimale et, par conséquent, nous ajoutons au plus deux fois de nombreux sommets que la taille de la couverture de sommet minimale.