Time-approximation trade-offs for inapproximable problems
作者：
Highlights：
• Some problems are very hard to approximate in polynomial time.
• We consider these problems in the context of sub-exponential time.
• We give (often tight) trade-offs between time and approximation.
摘要
•Some problems are very hard to approximate in polynomial time.•We consider these problems in the context of sub-exponential time.•We give (often tight) trade-offs between time and approximation.
论文关键词：Approximation algorithms,Exponential algorithms,Sub-exponential algorithms,Hardness of approximation
论文评审过程：Received 14 September 2016, Revised 20 August 2017, Accepted 18 September 2017, Available online 9 October 2017, Version of Record 13 November 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.09.009
