A polynomial-time algorithm to determine BCC efficient frontier without solving a mathematical programming problem

In this paper, we restrict our attention to the efficient frontier of the BCC model, where the BCC model is a well-known basic model in Data Envelopment Analysis (DEA). We here assume that each Decision Making Unit (DMU) has one input and one output. In order to obtain BCC efficient frontier, the paper proposes a polynomial-time algorithm of complexity bonded by O(n^3) to produce well-behaved affine functions. The produced functions are then used to determine a point-wise minimum of a finite number of affine functions. It will be shown that by finding this function, we in fact also determine the efficient frontier of the BCC model. The main advantage of this approach is ability to achieve the efficient frontier, without solving a mathematical programming problem. Also, all of the Pareto efficient DMUs, as BCC-efficient DMUs, can be easily obtained using the proposed algorithm. A numerical example is presented to explain the use and effectiveness of the proposed algorithm.