A Complexity-theoretic Analysis of Green Pickup-and-Delivery Problems
Authors: Xing Tan, Jimmy Xiangji Huang11990-11997
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | A Complexity-Theoretic Analysis of Green Pickup-and-Delivery Problems. Nevertheless, we demonstrate in this paper an inherent intractability of these green components themselves. More precisely, we show that GPD problems whose total constraints are reduced to almost the green ones only, remain to be NP-complete in the strong sense. We figure out a specifically constrained variant of GPD that, however, is weakly NP-complete a practical pseudo-polynomial time algorithm solving the variant problem is identified. |
| Researcher Affiliation | Academia | Xing Tan and Jimmy Xiangji Huang Information Retrieval and Knowledge Management Research Lab York University, Toronto, Ontario, Canada {xtan, jhuang}@yorku.ca |
| Pseudocode | Yes | Algorithm 1: A Pseudo-polynomial Time Solver |
| Open Source Code | No | The paper does not provide any statement or link indicating the release of source code for the described methodology. |
| Open Datasets | No | The paper focuses on theoretical complexity analysis and algorithm design for GPD variants, not on empirical studies using datasets. It uses mathematical problem instances and examples (e.g., from PARTITION, DHC) for proofs, but not in the context of publicly available datasets for training/testing. |
| Dataset Splits | No | The paper does not describe empirical experiments with data splits (training, validation, test sets). The work is theoretical, focusing on complexity proofs and algorithm analysis. |
| Hardware Specification | No | The paper does not mention any specific hardware specifications used for conducting experiments or running the described algorithms. The work is primarily theoretical. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers. The algorithm presented (Algorithm 1) is a conceptual pseudo-polynomial time solver rather than an implemented system with specific software requirements. |
| Experiment Setup | No | The paper does not describe an experimental setup with hyperparameters or system-level training settings. The work is theoretical, focused on complexity analysis and algorithm design rather than empirical performance evaluation. |