The Range Constrained NP-complete Problem And Design Of Approximation Algorithms

Punnen and Nair considered the range constrained optimization problem, which is defined as follows:given a finite set E, and a family of subsets of E, i.e.F 2E, the members of F are called feasible solutions, w and c are two positive real functions which defined on the E, i.e. w, c:E �' R+, we are asked to find a S∈F to satisfy w(S)≤D, the objective is to minimize c(S), where for each S ∈F, denote w(S)=maxe∈s w(e) -minees w(e), c(S)=∑eeSc(e). When the minimum weight sum optimization problem can be solved in polynomial time, Punnen and Nair designed a polynomial-time algorithm to solve the range constrained optimization problem. When D=+oo, the range constrained optimization problem becomes the minimum weight sum optimization problem, and if the latter problem is NP-complete, the former is also NP-complete.To our knowledge by now, however, when the minimum weight sum optimiza-tion problem is NP-complete, such range constrained optimization problem has not been studied. For this reason, when there is a ρ-approximation algorithm for the minimum weight sum optimization problem, we design a p-approximation algorith-m to solve the range constrained optimization NP-complete problem, where p is a ratio of the approximation algorithm for the minimum weight sum optimization problem.