Parameterized Algorithms for MILPs with Small Treedepth
Authors: Cornelius Brand, Martin Koutecký, Sebastian Ordyniak12249-12257
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we extend this line of work to the mixed case, by showing an algorithm solving MILP in time f(a, d) poly(n), where a is the largest coefficient of the constraint matrix, d is its treedepth, and n is the number of variables. This is enabled by proving bounds on the denominators (fractionality) of the vertices of bounded-treedepth (non-integer) linear programs. |
| Researcher Affiliation | Academia | Cornelius Brand,1 Martin Kouteck y,1 Sebastian Ordyniak,2 1 Computer Science Institute, Charles University, Prague, Czech Republic, 2 School of Computing, University of Leeds, United Kingdom |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not use or reference any datasets. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup or hyperparameters. |