International Journal of Foundations of Computer Science, Volume (29), No (7), Year (2018-11) , Pages (1231-1245)

Title : ( The Computational Complexity of and Approximation Algorithms for Variants of the Component Selection Problem )

Authors: Mostafa Nouri Baygi ,

Citation: BibTeX | EndNote

Abstract

In the past decades, there has been a burst of activity to simplify implementation of complex software systems. The solution framework in software engineering community for this problem is called component-based software design (CBSD), whereas in the modeling and simulation community it is called composability. Composability is a complex feature due to the challenges of creating components, selecting combinations of components, and integrating the selected components. In this paper, we address the challenge through the analysis of Component Selection (CS), the NP-complete process of selecting a minimal set of components to satisfy a set of objectives. Due to the computational complexity of CS, we consider approximation algorithms that make the component selection process practical. We define three variations of CS and present good approximation algorithms to find near optimal solutions. In spite of our creation of approximable variants of Component Selection, we prove that the general Component Selection problem is inapproximable.

Keywords

, Component selection; approximation algorithms; NP, completeness; set cover; red, blue set cover
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@article{paperid:1071843,
author = {Nouri Baygi, Mostafa},
title = {The Computational Complexity of and Approximation Algorithms for Variants of the Component Selection Problem},
journal = {International Journal of Foundations of Computer Science},
year = {2018},
volume = {29},
number = {7},
month = {November},
issn = {0129-0541},
pages = {1231--1245},
numpages = {14},
keywords = {Component selection; approximation algorithms; NP-completeness; set cover; red-blue set cover},
}

[Download]

%0 Journal Article
%T The Computational Complexity of and Approximation Algorithms for Variants of the Component Selection Problem
%A Nouri Baygi, Mostafa
%J International Journal of Foundations of Computer Science
%@ 0129-0541
%D 2018

[Download]