The maximum saving partition problem

The input to the MAXIMUM SAVING PARTITION PROBLEM consists of a set V={1,…,n}, weights wi, a function f, and a family S of feasible subsets of V. The output is a partition (S1,…,Sl) such that Si∈S, and ∑j∈Vwj-∑i=1lf(Si) is maximized. We present a general 12-approximation algorithm, and improved algorithms for special cases of the function f.