| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10524098 | Operations Research Letters | 2005 | 7 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Refael Hassin, Jérôme Monnot,