On the optimality of exact and approximation algorithms for scheduling problems

ما مسائل برنامه ریزی کلاسیک را در ماشین های موازی یکسانی به کار می گیریم تا مینیمال را به حداقل برسانیم. سابقه طولانی مطالعه در مورد این مشکل وجود دارد، تمرکز بر الگوریتم دقیق و تقریبی. بدین ترتیب طبیعی است که در نظر بیاوریم که آیا این الگوریتم ها بتوانند از لحاظ زمان اجرا بهبود یابند. ما محدودیت های پایه قوی را در زمان اجرا برنامه دقیق و تقریبی برای مسائل برنامه ریزی کلاسیک براساس فرضیه نمایشگاه ارائه می کنیم که نشان می دهد تقریب شناخته شده ترین و دقیق ترین الگوریتم ها تقریبا بهترین زمان ممکن از لحاظ زمان است.