Distribution-specific-approximation-guarantees