Efficient Web Service Composition via Knapsack-Variant Algorithm
This addresses the need for efficient web service composition algorithms as the number of services increases, but it is incremental as it builds on existing knapsack-based approaches.
The paper tackles the problem of minimizing the number of web services in compositions while satisfying user requests, and the proposed knapsack-variant algorithm outperforms state-of-the-art methods by generating solutions with the same or fewer services and much higher efficiency, as shown in experiments on eight public datasets.
Since the birth of web service composition, minimizing the number of web services of the resulting composition while satisfying the user request has been a significant perspective of research. With the increase of the number of services released across the Internet, seeking efficient algorithms for this research is an urgent need. In this paper we present an efficient mechanism to solve the problem of web service composition. For the given request, a service dependency graph is firstly generated with the relevant services picked from an external repository. Then, each search step on the graph is transformed into a dynamic knapsack problem by mapping services to items whose volume and cost is changeable, after which a knapsack-variant algorithm is applied to solve each problem after transformation. Once the last search step is completed, the minimal composition that satisfies the request can be obtained. Experiments on eight public datasets proposed for the Web Service Challenge 2008 shows that the proposed mechanism outperforms the state-of-the-art ones by generating solutions containing the same or smaller number of services with much higher efficiency.