Su una pre-fase di lavorazione per primaria alla doppia pesata impostare coprire problema

Question

Stavo leggendo il paper dal titolo "Primal-dual RNC algoritmi di approssimazione"da Rajagopalan e Vazirani.Ho un problema di comprensione Lemma 4.1.1.

Essi presentano un dual montaggio basato su algoritmo per ponderati set di copertura.Prima mi permetta di impostare la richiesta concetto di chiarire dove sto avendo problemi.Supponiamo di avere $n$ elementi ($U$) e $m$ set di$S$).Ogni set ha un positivo di peso.Lasciate $E_v$ detiene il set in cui l'elemento $v$ è presente.Lasciate $\beta =$max$_{v \in U}$ min$_{s \in E_v}$ peso(s).Lasciate che anche $IP^*$ è il peso di un insieme ottimale di copertura.È facile vedere, $IP^*\geq \beta$.

Ora supponiamo di avere un algoritmo di approssimazione per ponderati set di copertura.Che cosa è la carta dice nel lemma è che si può fare un pre-trattamento prima di iniziare il ravvicinamento algoritmo come segue.È possibile eseguire la scansione attraverso il set e aggiungere qualsiasi tipo di imposta che hanno peso $\leq \beta/n$.Dato che ci sono $n$ elementi il costo aggiuntivo è di al massimo $\beta$.Poi dicono che

Dal $\beta$ è un limite inferiore $IP^*$, questo costo è sussunto nell'approssimazione.E questa è la frase che non ho capito.