Balanced optimization problems

Suppose we are given a finite set E, a family F of ‘feasible’ subsets of E and a real weight c(e) associated with every e?E. We consider the problem of finding S?F for which max {c(e)?c(e′): e, e′ ?S} is minimized. In other words, the differenc value between the largest and smallest value used should be as small as possible. We show that if we can efficiently answer the feasibility question then we can efficiently solve the optimization problem. We specialize these results to assignment problems and thereby obtain on O(n⁴) algorithm for ‘balanced’ assignment problems.