|
|||||
|
|
Designing PTASs for MIN-SUM scheduling problems |
|
| Authors: | F. Afrati |
| Affiliation: | a NTU Athens, School of Electrical and Computer Engineering, Heroon Polytechniou 9, 15773, Athens, Greece b Athens University of Economics and Business, Department of Informatics, Patission 76, 10434 Athens, Greece |
| Abstract: | 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. |
| Keywords: | Scheduling MIN-SUM criteria Approximation algorithms PTASs |
| 本文献已被 ScienceDirect 等数据库收录！ | |