Abstract: The optimal competence set expansion problem is to minimize the total acquiring cost in an expansion process from a set of existing skills to a set of required skills. A numerical approach based on integer programming has been developed in the literature. In this paper we establish a directed network connection model and propose a combinatorial optimization approach for the problem. The main results have been proved: 1)  the problem is strongly NP-hard;  2)  the problem can be solved in polynomial time if the number of intermediate vertices is a constant;  3)  the problem admits an  approximation algorithm of performance ratio 2. Moreover, an exact algorithm (branch-and-bound algorithm) and heuristic algorithms are provided.

Key words: competence set, NP-completeness, polynomial-time algorithm, exact algorithm; approximation algorithm