QoS-based service selection aims at finding the best component services that satisfy the end-to-end quality requirements. The problem can be modeled as a multi-dimension multi-choice 0-1 knapsack problem, which is known as NP-hard. Recently published solutions propose using linear programming techniques to solve the problem. However, the poor scalability of linear program solving methods restricts their applicability to small-size problems and renders them inappropriate for dynamic applications with run-time requirements. In this paper, we address this problem and propose a scalable QoS computation approach based on a heuristic algorithm, which decomposes the optimization problem into small sub-problems that can be solved more efficiently than the original problem. Experimental evaluations show that near-to-optimal solutions can be found using our algorithm much faster than using linear programming methods.
%0 Book Section
%1 alrifai2009scalable
%A Alrifai, Mohammad
%A Risse, Thomas
%A Dolog, Peter
%A Nejdl, Wolfgang
%B Service-Oriented Computing – ICSOC 2008 Workshops
%D 2009
%E Feuerlicht, George
%E Lamersdorf, Winfried
%I Springer Berlin Heidelberg
%K Webservice myown qos scalable
%P 190-199
%R 10.1007/978-3-642-01247-1_20
%T A Scalable Approach for QoS-Based Web Service Selection
%U http://www.l3s.de/~risse/pub/QoSCSOA.pdf
%V 5472
%X QoS-based service selection aims at finding the best component services that satisfy the end-to-end quality requirements. The problem can be modeled as a multi-dimension multi-choice 0-1 knapsack problem, which is known as NP-hard. Recently published solutions propose using linear programming techniques to solve the problem. However, the poor scalability of linear program solving methods restricts their applicability to small-size problems and renders them inappropriate for dynamic applications with run-time requirements. In this paper, we address this problem and propose a scalable QoS computation approach based on a heuristic algorithm, which decomposes the optimization problem into small sub-problems that can be solved more efficiently than the original problem. Experimental evaluations show that near-to-optimal solutions can be found using our algorithm much faster than using linear programming methods.
%@ 978-3-642-01246-4
@incollection{alrifai2009scalable,
abstract = {QoS-based service selection aims at finding the best component services that satisfy the end-to-end quality requirements. The problem can be modeled as a multi-dimension multi-choice 0-1 knapsack problem, which is known as NP-hard. Recently published solutions propose using linear programming techniques to solve the problem. However, the poor scalability of linear program solving methods restricts their applicability to small-size problems and renders them inappropriate for dynamic applications with run-time requirements. In this paper, we address this problem and propose a scalable QoS computation approach based on a heuristic algorithm, which decomposes the optimization problem into small sub-problems that can be solved more efficiently than the original problem. Experimental evaluations show that near-to-optimal solutions can be found using our algorithm much faster than using linear programming methods.},
added-at = {2014-03-10T18:05:17.000+0100},
author = {Alrifai, Mohammad and Risse, Thomas and Dolog, Peter and Nejdl, Wolfgang},
biburl = {https://www.bibsonomy.org/bibtex/26f7b9f634047f585b2d5c3637cadb4fa/trisse69},
booktitle = {Service-Oriented Computing – ICSOC 2008 Workshops},
doi = {10.1007/978-3-642-01247-1_20},
editor = {Feuerlicht, George and Lamersdorf, Winfried},
interhash = {a77ab42ce8aa5c812c46d212d00f778d},
intrahash = {6f7b9f634047f585b2d5c3637cadb4fa},
isbn = {978-3-642-01246-4},
keywords = {Webservice myown qos scalable},
pages = {190-199},
publisher = {Springer Berlin Heidelberg},
series = {Lecture Notes in Computer Science},
timestamp = {2014-11-18T16:56:13.000+0100},
title = {A Scalable Approach for QoS-Based Web Service Selection},
url = {http://www.l3s.de/~risse/pub/QoSCSOA.pdf},
volume = 5472,
year = 2009
}