概念多项式时间近似方案 / Polynomial-time approximation scheme
PTAS
一种近似算法框架,对任意给定的ε>0,能在多项式时间内给出(1+ε)-近似解。PTAS的存在性意味着问题可以任意逼近最优解。
时间轴 (近 90 天)
11月5日
APX-hard问题不存在多项式时间近似方案(PTAS),除非P=NP。
待验证50%
一种近似算法框架,对任意给定的ε>0,能在多项式时间内给出(1+ε)-近似解。PTAS的存在性意味着问题可以任意逼近最优解。
APX-hard问题不存在多项式时间近似方案(PTAS),除非P=NP。