• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
icsoc15.pdf (415.1Kb)
Type
Communication / Conférence
Date
2015
Conference title
13th International Conference on Service-Oriented Computing, ICSOC 2015
Conference date
2015-11
Conference city
Goa
Conference country
India
Book title
Service-Oriented Computing. 13th International Conference, ICSOC 2015, Goa, India, November 16-19, 2015, Proceedings
Book author
Barros, Alistair; Grigori, Daniela; Narendra, Nanjangud C.; Dam, Hoa Khanh
Publisher
Springer
Published in
Berlin
ISBN
978-3-662-48615-3
Pages
345-352
Publication identifier
10.1007/978-3-662-48616-0_23
Metadata
Show full item record
Author(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 cc
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 workflows

Related items

Showing items related by title and author.

  • Thumbnail
    TQoS: Transactional and QoS-Aware Selection Algorithm for Automatic Web Service Composition 
    El Haddad, Joyce; Manouvrier, Maude; Rukoz, Marta (2010) Article accepté pour publication ou publié
  • Thumbnail
    On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism 
    Abu-Khzam, Faisal N.; Bonnet, Édouard; Sikora, Florian (2015) Communication / Conférence
  • Thumbnail
    On the complexity of various parameterizations of common induced subgraph isomorphism 
    Abu-Khzam, Faisal N.; Bonnet, Édouard; Sikora, Florian (2017) Article accepté pour publication ou publié
  • Thumbnail
    Optimization Techniques for QoS-Aware Workflow Realization in Web Services Context 
    El Haddad, Joyce (2012) Communication / Conférence
  • Thumbnail
    Parameterized Dynamic Variants of Red-Blue Dominating Set 
    Abu-Khzam, Faisal; Bazgan, Cristina; Fernau, Henning (2020) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo