The maximum saving partition problem |
| |
| Authors: | Refael Hassin |
| |
| Institution: | a Department of Statistics and Operations Research, Tel-Aviv University, Tel Aviv 69978, Israel
b LAMSADE CNRS, Université Paris-Dauphine, France |
| |
| 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  is maximized. We present a general  -approximation algorithm, and improved algorithms for special cases of the function f. |
| |
| Keywords: | Partitioning Color saving Approximation algorithms NP-complete |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
