On optimality of exact and approximation algorithms for scheduling problems

zum Volltext (626 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • Juni 2013
Seitenbereich49. S

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. Under the exponential time hypothesis (ETH), lower bounds on the running times of exact and approximation algorithms are characterized.
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000034
 
URN:NBNurn:nbn:de:101:1-2013061921232
IDNummer des Berichts :
  • TR_1303