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