Object Reachability via Swaps along a Line
Authors: Sen Huang, Mingyu Xiao2037-2044
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We answer this open problem positively by giving a polynomial-time algorithm. Furthermore, we show that the problem on a path will become NP-hard when the preferences of the agents are weak (ties are allowed). |
| Researcher Affiliation | Academia | Sen Huang, Mingyu Xiao School of Computer Science and Engineering University of Electronic Science and Technology of China |
| Pseudocode | Yes | Algorithm 1: Main steps to solve STRICT OBJECT REACHABILITY in a path |
| Open Source Code | No | No statement about making the source code publicly available was found. |
| Open Datasets | No | The paper describes a theoretical algorithm and proves NP-hardness, and does not involve empirical evaluation on a dataset that would require public access. |
| Dataset Splits | No | The paper describes a theoretical algorithm and proofs, and does not involve experimental validation on data with specified splits. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments run on specific hardware. |
| Software Dependencies | No | The paper mentions using 'solvers for the 2-SAT problem' and refers to 'the O(n+m)-time algorithm for 2-SAT (Aspvall, Plass, and Tarjan 1979)', but does not provide specific version numbers for any software dependencies. |
| Experiment Setup | No | The paper describes a theoretical algorithm and its complexity, and does not provide details on experimental setup such as hyperparameters or training configurations. |