Charles Darwin University

CDU eSpace
Institutional Repository

CDU Staff and Student only

On the Complexity of QoS-Aware Service Selection Problem

Abu-Khzam, Faisal N., Bazgan, Cristina, El Haddad, Joyce and Sikora, Florian (2015). On the Complexity of QoS-Aware Service Selection Problem. In: 13th International Conference, ICSOC 2015, Goa, India, 16 - 19 November 2015.

Document type: Conference Paper
Citation counts: Google Scholar Search Google Scholar

IRMA ID 83393865xPUB230
Author Abu-Khzam, Faisal N.
Bazgan, Cristina
El Haddad, Joyce
Sikora, Florian
Title On the Complexity of QoS-Aware Service Selection Problem
Conference Name 13th International Conference, ICSOC 2015
Conference Location Goa, India
Conference Dates 16 - 19 November 2015
Conference Publication Title Lecture Notes in Computer Science
Place of Publication Germany
Publisher Springer
Publication Year 2015
Volume Number 9435
ISBN 978-3-662-48616-0   (check CDU catalogue open catalogue search in new window)
ISSN 0302-9743   (check CDU catalogue open catalogue search in new window)
Start Page 345
End Page 352
Total Pages 8
HERDC Category E1 - Conference Publication (DIISR)
Abstract This paper addresses the QoS-aware service selection problem considering complex workflow patterns. More specifically, it focuses on the complexity issues of the problem. The NP -hardness of the problem, under various settings, has been open for many years and has never been addressed thoroughly. We study the problem complexity depending on the workflow structure, the number of workflow tasks, the number of alternative services per task and the categories of quality of service criterion associated to services. We provide for the first time the NP -hardness proof of the problem. Additionally, we show that the problem is polynomial in case of only one criterion per task and pseudo-polynomial if there is a fixed number of criteria.
Keyword Quality of Service
Service selection
Complex workflows
Description for Link Link to published version
Version Filter Type
Access Statistics: 192 Abstract Views  -  Detailed Statistics
Created: Tue, 26 Jul 2016, 12:12:28 CST