Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
The Complexity Landscape of Resource-Constrained Scheduling
Authors: Robert Ganian, Thekla Hamm, Guillaume Mescoff
IJCAI 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In the first part of our paper, we develop new algorithms and give hardness-proofs in order to obtain a detailed complexity map of (M)RCPSP that settles the complexity of all 1024 considered variants of the problem defined in terms of explicit restrictions of natural parameters of instances. In the second part, we turn to implicit structural restrictions defined in terms of the complexity of interactions between individual activities. In particular, we show that if the treewidth of a graph which captures such interactions is bounded by a constant, then we can solve MRCPSP in polynomial time. |
| Researcher Affiliation | Academia | Robert Ganian1 , Thekla Hamm1 and Guillaume Mescoff2 1Vienna University of Technology 2Rennes University EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper describes algorithms and proof sketches in prose but does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described. |
| Open Datasets | No | The paper is purely theoretical, focusing on complexity analysis and algorithms, and does not use or refer to any datasets. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments requiring dataset splits (training, validation, test). |
| Hardware Specification | No | The paper is theoretical and does not report on experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and describes algorithms abstractly; it does not mention specific ancillary software details or version numbers required for replication. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup, such as hyperparameters or training configurations. |