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