AN EPSILON-APPROXIMATION SCHEME FOR COMBINATORIAL OPTIMIZATION PROBLEMS WITH MINIMUM VARIANCE CRITERION

Suppose that we are given a finite set E, a family of feasible subsets of E and a real cost associated with each element in E. This paper considers the problem of finding a feasible subset such that the variance of the costs of elements in the subset is minimum among all feasible subsets. We consider the case in which the number of elements in a feasible subset is a constant, i.e., it does not depend on the choice of the subset. This paper first exhibits a parametric characterization of an optimal solution of the above minimum variance 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 variance problem.