The maximum saving partition problem

0.00 Avg rating—0 Votes

Article ID:	iaor20051974
Country:	Netherlands
Volume:	33
Issue:	3
Start Page Number:	242
End Page Number:	248
Publication Date:	May 2005
Journal:	Operations Research Letters
Authors:	Hassin Refael, Monnot Jrme
Keywords:	networks: scheduling

Abstract:

The input to the maximum saving partition problem consists of a set V=1,…,n, weights wi, a function ƒ, and a family S of feasible subsets of V. The output is a partition (S1,…,Sl) such that Si∈S, and ∑j∈V ωj − ∑^li=1 ƒ(Si) is maximized. We present a general 1/2-approximation algorithm, and improved algorithms for special cases of the function ƒ.

Reviews

Required fields are marked *. Your email address will not be published.