On the Complexity of QoS-Aware Service Selection Problem

Faisal Abu Khzam, Cristina Bazgan, J El Haddad, Florian Sikora

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review


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.
Original languageEnglish
Title of host publicationInternational Conference on Service-Oriented Computing ICSOC 2015
Subtitle of host publicationService-Oriented Computing
EditorsA. Barros , D. Grigori , N. Narendra , H. Dam
Place of PublicationGermany
Number of pages8
ISBN (Electronic)978-3-662-48616-0
ISBN (Print)978-3-662-48615-3
Publication statusPublished - 2015
Externally publishedYes
EventInternational Conference on Service-Oriented Computing (ICSOC 2015 13th) - Goa, India
Duration: 16 Nov 201519 Nov 2015
Conference number: 2015

Publication series

NameLecture Notes in Computer Science
ISSN (Electronic)0302-9743


ConferenceInternational Conference on Service-Oriented Computing (ICSOC 2015 13th)
Abbreviated titleICSOC


Dive into the research topics of 'On the Complexity of QoS-Aware Service Selection Problem'. Together they form a unique fingerprint.

Cite this