
On the Complexity of QoS-Aware Service Selection Problem
Abu-Khzam, Faisal N.; Bazgan, Cristina; El Haddad, Joyce; Sikora, Florian (2015), On the Complexity of QoS-Aware Service Selection Problem, in Barros, Alistair; Grigori, Daniela; Narendra, Nanjangud C.; Dam, Hoa Khanh, Service-Oriented Computing. 13th International Conference, ICSOC 2015, Goa, India, November 16-19, 2015, Proceedings, Springer : Berlin, p. 345-352. 10.1007/978-3-662-48616-0_23
View/ Open
Type
Communication / ConférenceDate
2015Conference title
13th International Conference on Service-Oriented Computing, ICSOC 2015Conference date
2015-11Conference city
GoaConference country
IndiaBook title
Service-Oriented Computing. 13th International Conference, ICSOC 2015, Goa, India, November 16-19, 2015, ProceedingsBook author
Barros, Alistair; Grigori, Daniela; Narendra, Nanjangud C.; Dam, Hoa KhanhPublisher
Springer
Published in
Berlin
ISBN
978-3-662-48615-3
Pages
345-352
Publication identifier
Metadata
Show full item recordAuthor(s)
Abu-Khzam, Faisal N.Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
El Haddad, Joyce
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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.Subjects / Keywords
Complexity; Quality of Service; Service selection; Optimization; Complex workflowsRelated items
Showing items related by title and author.
-
El Haddad, Joyce; Manouvrier, Maude; Rukoz, Marta (2010) Article accepté pour publication ou publié
-
Abu-Khzam, Faisal N.; Bonnet, Édouard; Sikora, Florian (2015) Communication / Conférence
-
Abu-Khzam, Faisal N.; Bonnet, Édouard; Sikora, Florian (2017) Article accepté pour publication ou publié
-
El Haddad, Joyce (2012) Communication / Conférence
-
Abu-Khzam, Faisal; Bazgan, Cristina; Fernau, Henning (2020) Communication / Conférence