A Fast Algorithm for Consistency Checking Partially Ordered Time
Authors: Leif Eriksson, Victor Lagerkvist
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We construct a much faster algorithm with a run-time bounded by O ((0.26n)n). This is achieved by a sophisticated enumeration of structures similar to total orders, which are then greedily expanded towards a solution. The algorithm, in particular, organizes variables into pairs where we only have to consider a relative ordering with n 2 other variables. This scheme leads to a runtime that is dominated by n!/2 n 2 . Demonstrating the correctness of this strategy is a nontrivial task, and the analysis itself is arguably as interesting as the precise bound we attain. |
| Researcher Affiliation | Academia | Leif Eriksson and Victor Lagerkvist Department of Computer and Information Science, Link oping University, Link oping, Sweden {leif.eriksson, victor.lagerkvist}@liu.se |
| Pseudocode | No | No structured pseudocode or clearly labeled algorithm blocks were found. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the methodology described. |
| Open Datasets | No | This is a theoretical paper and does not involve empirical evaluation on datasets. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical evaluation on datasets, thus no dataset split information for validation is provided. |
| Hardware Specification | No | This is a theoretical paper and does not report on experiments requiring hardware specifications. |
| Software Dependencies | No | This is a theoretical paper and does not report on experiments requiring specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not report on experiments requiring detailed experimental setup or hyperparameters. |