On the optimality of exact and approximation algorithms for scheduling problems

作者：

Highlights：

• We provide lower bounds on the running time of approximation schemes for scheduling under exponential time hypothesis.

• Our lower bounds match the running time of the best-known algorithms for scheduling so far and are thus tight.

摘要

•We provide lower bounds on the running time of approximation schemes for scheduling under exponential time hypothesis.•Our lower bounds match the running time of the best-known algorithms for scheduling so far and are thus tight.

论文关键词：Approximation schemes,Scheduling,Lower bounds,Exponential time hypothesis

论文评审过程：Received 24 April 2015, Revised 13 August 2016, Accepted 26 March 2018, Available online 20 April 2018, Version of Record 31 May 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.03.005