À propos d'une étape de prétraitement pour le problème de couverture de set Primal-dual pondéré

Question

Je lisais le journal intitulé "Algorithmes d'approximation RNC primal-dual"Par Rajagopalan et Vazirani. J'ai un problème de compréhension du lemme 4.1.1.

Ils présentent un algorithme à double ajustement pour le couvercle de jeu pondéré. Permettez-moi d'abord de configurer le concept requis pour clarifier où j'ai des problèmes. Supposons que nous ayons $ n $ éléments ($ U $) et $ m $ ensembles ($ S $). Chaque ensemble a un poids positif. Laisser $ E_v $ tient les ensembles dans lesquels l'élément $ v $ est présent. Laisser $ bêta = $max$ _ {v in u} $ min$ _ {s in e_v} $ poids (s). Laisser aussi $ Ip ^ * $ est le poids d'une couverture de jeu optimale. C'est facile à voir, $ Ip ^ * geq beta $.

Supposons maintenant que nous avons un algorithme d'approximation pour le couvercle de set pondéré. Ce que le document dit dans le lemme, c'est que vous pouvez faire un prétraitement avant de commencer l'algorithme d'approximation comme suit. Vous pouvez scanner les ensembles et ajouter tous les ensembles qui ont du poids $ leq beta / n $. Puisqu'il y a $ n $ Éléments Le coût supplémentaire est au plus $ bêta $. Ensuite, ils prétendent que

Depuis $ bêta $ est une limite inférieure sur $ Ip ^ * $, ce coût est subsumé dans l'approximation. Et c'est la déclaration que je n'ai pas compris.