Approximating Component Selection

Simulation composability is a difficult capability to achieve due to the challenges of creating components, selecting combinations of components, and integrating the selected components. We address the second of these challenges through 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 high order of computational complexity of CS, we examine approximating solutions that make the CS process practicable. We define two variations of CS and prove that good approximations to optimal solutions result from applying a standard Greedy selection algorithm to each. Despite our creation of approximable variations of CS, we conjecture that any proof of the inapproximability of CS will reveal theoretical limitations of its practicality. We conclude that reasonably constrained variations of CS can be solved satisfactorily, and efficiently, but more general cases appear to never be solvable in a similar manner.