The Complexity Landscape of Resource-Constrained Scheduling
Authors: Robert Ganian, Thekla Hamm, Guillaume Mescoff
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | 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 rganian@gmail.com, thamm@ac.tuwien.ac.at, guillaume.mescoff@ens-rennes.fr |
| 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. |