Designing PTASs for MIN-SUM scheduling problems ?
We review approximability and inapproximability results for MIN-SUM scheduling problems and we focus on techniques for designing polynomial time approximation schemes for this class of problems. We present examples which illustrate the efficient use of the ratio partitioning and time partitioning techniques.
ptass scheduling min-sum criteria approximation algorithms