In service-oriented systems, context information can be used to select a variety of services to support the execution of processes. Yet, context information causes interdependencies between services, in the sense that they are evaluated differently – regarding their utility and feasibility - when being composed with other services. Such context interdependencies have not been sufficiently addressed by research so far, as approaches either disregard them or propose exact solutions which are hardly applicable due to high time complexity of the selection problem. To alleviate this drawback, we present a heuristic technique considering context interdependencies. In particular, this technique consists of an approach to decompose end-to-end constraints together with a local selection approach. Our evaluation, by means of a real-world data, shows that this technique achieves close to optimal selection results at a fraction of the computation time of an exact solution and thus contributes to an efficient decision support.