| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6853046 | Artificial Intelligence | 2018 | 11 Pages |
Abstract
In particular, we show that ILP is fixed-parameter tractable when parameterized by the treedepth of the constraint matrix and the maximum absolute value of any coefficient occurring in the ILP instance. Together with matching hardness results for the more general parameter treewidth, we give an overview of the complexity of ILP w.r.t. decompositional parameters defined on the constraint matrix.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Robert Ganian, Sebastian Ordyniak,