In Quality-Driven Service Composition, tasks from an ab- stract work ow are assigned to concrete services such that work ow QoS are optimized. The following three proper- ties are desirable for a corresponding algorithm. First, the run time is ideally bounded by a polynomial in the number of work ow tasks and service candidates. Second, the algo- rithm provides formal guarantees on how close the returned solution is to the optimal one. Third, the algorithm is able to return a representative set of Pareto-optimal solutions instead of only one. The user can choose among them or apply arbitrary lter or sort operations in successive steps. We present the rst algorithm that has all three features. We analyze its formal properties and evaluate the algorithm experimentally. We nd that our algorithm is competitive from the theoretical as well as from the practical perspec- tive.