Suppose that a finite set E, a family of feasible subsets of E and a nonnegative cost and a reliability associated with each element in E are given. This paper considers the problem of finding a feasible subset such that the cost-reliability ratio of the subset is minimum among all feasible subsets. This paper first exhibits a parametric characterization of an optimal solution of this problem. Based on this characterization, it is shown that if one can solve in polynomial time the problem of finding a feasible subset that minimizes the sum of costs in the subset, it is possible to construct a fully polynomial time approximation scheme for the above minimum cost-reliability ratio problem.
