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.
| Original language | English |
|---|---|
| Title of host publication | International Conference on Service-Oriented Computing ICSOC 2015 |
| Subtitle of host publication | Service-Oriented Computing |
| Editors | A. Barros , D. Grigori , N. Narendra , H. Dam |
| Place of Publication | Germany |
| Publisher | Springer |
| Pages | 345-352 |
| Number of pages | 8 |
| Volume | 9435 |
| ISBN (Electronic) | 978-3-662-48616-0 |
| ISBN (Print) | 978-3-662-48615-3 |
| Publication status | Published - 2015 |
| Externally published | Yes |
| Event | International Conference on Service-Oriented Computing (ICSOC 2015 13th) - Goa, India Duration: 16 Nov 2015 → 19 Nov 2015 Conference number: 2015 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 9435 |
| ISSN (Electronic) | 0302-9743 |
Conference
| Conference | International Conference on Service-Oriented Computing (ICSOC 2015 13th) |
|---|---|
| Abbreviated title | ICSOC |
| Country/Territory | India |
| City | Goa |
| Period | 16/11/15 → 19/11/15 |