This paper gives a lucid and detailed derivation and implementation of efficient algorithms for solving a selection problem for Web services arising whenever one has to combine several services out of a larger set of available services so as to ensure some end-to-end constraints.

In this publication, the authors address quality of service (QoS) constraints, that is, the nonfunctional characteristics of services such as response time, execution time, throughput, availability, and costs. Clearly, when composing a larger composite service out of a set of atomic services, each individual service will contribute some amount to a particular end-to-end QoS threshold. The algorithms provided by the authors not only ensure that the final selection of atomic services meets all QoS constraints (for example, “total costs < 200"), but also optimize an additional variable, service utility.

The authors present two different approaches for solving this problem: mapping it to a multidimensional multichoice knapsack problem, and, unrelated to the former, using a 0-1 integer programming model for solving a multiconstrained optimal path problem. All algorithms are specified in meticulous detail (mathematical formulae, pseudocode, and flow charts), enabling readers to base their own implementations on this paper.

Actual implementations of the algorithms are investigated and discussed with regard to efficiency, which, in this context of nondeterministic polynomial-time (NP) complete problems, amounts to a tradeoff between running time and degree of optimality of the heuristically found solutions.

There are two things worth noting here. First, the authors openly discuss that their approach is not wholly new. However, in contrast to other publications, their algorithms are more general in nature and the clarity and readability of the paper definitely exceeds the average publication. Second, the authors unnecessarily limit the type of overall utility function to be optimized to a rather artificially weighted sum of QoS attributes. Unfortunately, they do not discuss that--without change--their algorithms also support the obvious generalization to arbitrary utility functions. Despite these minor details, I definitely recommend this paper.