Semantic Web service descriptions are typically multi-parameter constructs. Discovering semantically relevant services given a desirable service description is typically addressed by performing a pairwise, logic-based match between the requested and offered parameters. However, little or no attention is given to combining these partial results to compile the final list of candidate services. Instead, this is often done in an ad hoc manner, implying a priori assumptions regarding the user's preferences. In this paper, we focus on identifying the best candidate Semantic Web services given the description of a requested service. We model the problem as a skyline query, also known as the maximum vector problem, and we show how the service selection process can be performed efficiently. We consider different aspects of the service selection process, addressing both the requesters' and the providers' points of view. Experimental evaluation on real and synthetic data shows the effectiveness and efficiency of the proposed approach.