Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics
DOI10.1613/jair.1.12278zbMath1461.68213OpenAlexW3119810193MaRDI QIDQ5145837
Christer Bäckström, Peter Jonsson, Sebastian Ordyniak
Publication date: 22 January 2021
Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1613/jair.1.12278
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the hardness of approximating label-cover
- State-variable planning under structural restrictions: algorithms and complexity
- The computational complexity of propositional STRIPS planning
- Strong bounds on the approximability of two Pspace-hard problems in propositional planning
- Backdoors to planning
- Red-black planning: a new systematic approach to partial delete relaxation
- A complete parameterized complexity analysis of bounded planning
- Minimum propositional proof length is NP-hard to linearly approximate
- MANAGING TEMPORAL CYCLES IN PLANNING PROBLEMS REQUIRING CONCURRENCY
- Sound and Complete Landmarks for And/Or Graphs
- The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks
- Polylogarithmic inapproximability
- A Greedy Heuristic for the Set-Covering Problem
- Analysing Approximability and Heuristics in Planning Using the Exponential-Time Hypothesis
- Time and Space Bounds for Planning
- Approximation Algorithms for Directed Steiner Problems
- Steiner Tree Approximation via Iterative Randomized Rounding
- Monotone Temporal Planning: Tractability, Extensions and Applications
This page was built for publication: Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics
