Strong bounds on the approximability of two Pspace-hard problems in propositional planning

Authors
Jonsson, P
Citation
P. Jonsson, Strong bounds on the approximability of two Pspace-hard problems in propositional planning, ANN MATH A, 26(1-4), 1999, pp. 133-147
Citations number
22
Categorie Soggetti
Engineering Mathematics
Journal title
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
ISSN journal
10122443 → ACNP
Volume
26
Issue
1-4
Year of publication
1999
Pages
133 - 147
Database
ISI
SICI code
1012-2443(1999)26:1-4<133:SBOTAO>2.0.ZU;2-K
Abstract
The computational complexity of planning with Strips-style operators has re ceived a considerable amount of interest in the literature. However, the ap proximability of such problems has only received minute attention. We study two Pspace-hard optimization versions of propositional planning and provid e tight upper and lower bounds on their approximability.