In Search of Tractability for Partial Satisfaction Planning
Authors: Michael Katz, Vitaly Mirkis
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work we investigate the computational complexity of restricted fragments of two variants of partial satisfaction: net-benefit and oversubscription planning. In particular, we examine restrictions on the causal graph structure and variable domain size of the planning problem, and show that even for the strictest such restrictions, optimal oversubscription planning is hard. In contrast, certain tractability results previously obtained for classical planning also apply to net-benefit planning. |
| Researcher Affiliation | Industry | Michael Katz IBM Watson Health, Israel katzm@il.ibm.com Vitaly Mirkis Huawei Technologies, Israel vitaly.mirkis@huawei.com |
| Pseudocode | No | The paper describes algorithms verbally and through logical steps in proofs, but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is theoretical and does not mention any open-source code for its methodology. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not use validation splits. |
| Hardware Specification | No | The paper is theoretical and does not specify any hardware used. |
| Software Dependencies | No | The paper is theoretical and does not list any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system settings. |