Algoritmo di approssimazione per copertura set ponderata, utilizzando pesi moltiplicativi

Question

È noto che il problema della copertura del set frazionario può essere riformulato come un problema di programmazione lineare ed essere approssimato usando il metodo dei pesi moltiplicativi, ad esempio Questa nota di lezione mostra come farlo.
Il tempo di esecuzione dipende dalla "larghezza" del problema, che equivale al numero di insiemi nel caso non ponderato. Tuttavia, nel caso ponderato, la larghezza del problema dipende dalla funzione di peso, quindi il tempo di esecuzione è esponenziale rispetto alla rappresentazione del problema. C'è un modo per superare questo problema? O un modo per ridurlo al tempo di esecuzione polinomiale o alla prova che è impossibile (sotto ipotesi plausibili di complessità)?