The Complexity Landscape of Decompositional Parameters for ILP
Authors: Robert Ganian, Sebastian Ordyniak
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we initiate a similar line of research for ILP by studying the parameterized complexity of ILP w.r.t. various structural parameterizations. ... Our main algorithmic result (Theorem 5) shows that ILP is fixed-parameter tractable parameterized by the treedepth of the primal graph and the maximum absolute value ℓof any coefficient occurring in A or b. Together with the classical results for totally unimodular matrices (Papadimitriou and Steiglitz 1982, Section 13.2.) and fixed number of variables (Lenstra and Jr. 1983), which use entirely different techniques, our result is one of the surprisingly few tractability results for ILP in its full generality. We complete our complexity landscape (given in Table 1) with matching lower bounds, provided in terms of W[1]-hardness and para NP-hardness results |
| Researcher Affiliation | Academia | Robert Ganian and Sebastian Ordyniak TU Wien, Vienna, Austria |
| Pseudocode | No | The paper focuses on theoretical proofs and algorithmic results, but it does not include any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement about releasing source code or include a link to a code repository. |
| Open Datasets | No | The paper is purely theoretical, focusing on complexity and tractability of ILP, and does not involve any datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments with datasets, thus no training, validation, or test split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware, thus no hardware specifications (like GPU/CPU models or memory) are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational implementations or experiments that would list software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experiments or their setup, therefore no details like hyperparameters or training configurations are provided. |