Strong bounds on the approximability of two Pspace-hard problems in propositional planning
Strong bounds on the approximability of two Pspace-hard problems in propositional planning
复制标题
命题规划中两个 P 空间困难问题的逼近性的强界
DOI：
10.1023/a:1018954827926
复制
发表时间：
1999
影响因子：
1.2
通讯作者：
P. Jonsson
中科院分区：
文献类型：
--
作者：
P. Jonsson
使用STRIPS式算子进行规划的计算复杂性在文献中引起了相当大的兴趣。然而，这类问题的近似性只得到了极小的关注。我们研究了命题规划的两个PSPACE-Hard优化版本，并给出了它们的逼近性的上下界。
The computational complexity of planning with Strips-style operators has received a considerable amount of interest in the literature. However, the approximability of such problems has only received minute attention. We study two Pspace-hard optimization versions of propositional planning and provide tight upper and lower bounds on their approximability.