While Theorem REF  suggests to construct an \(\varepsilon \) -approximation simply by taking a uniform random sample from \(P\) , Theorem REF  requires us to take non-uniform sample where the distribution is defined by the importance \(s(\cdot )\) . Bounding these importances such that the sum \(t=\sum _{p\in P}s(p)\)  of importances will be small raise a new optimization problem that, as we will see in the next sections, might be not easy at all to solve. So what did we gain by proving Theorem REF  (or the framework of [1]} in general)?
