13th International CSI Computer Conference, CSICC 2008 Kish Island, Iran , 2008-03-09

Title : ( Approximating Component Selection With General Costs )

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 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 second 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 examine approximating solutions that make the CS 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 variations of Component Selection, we prove that the general Component Selection problem is inapproximable.

Keywords

, Component Selection, NP-Completeness, Set Cover, Approximation Algorithms, Red-Blue Set Cover
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@inproceedings{paperid:1038795,
author = {Nouri Baygi, Mostafa},
title = {Approximating Component Selection With General Costs},
booktitle = {13th International CSI Computer Conference, CSICC 2008 Kish Island, Iran},
year = {2008},
location = {کیش, IRAN},
keywords = {Component Selection; NP-Completeness; Set Cover; Approximation Algorithms; Red-Blue Set Cover},
}

[Download]

%0 Conference Proceedings
%T Approximating Component Selection With General Costs
%A Nouri Baygi, Mostafa
%J 13th International CSI Computer Conference, CSICC 2008 Kish Island, Iran
%D 2008

[Download]