Contributions to Proceedings:
E. Eiben, R. Ganian, D. Knop:
"Unary Integer Linear Programming with Structural Restrictions";
in: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence",
International Joint Conferences on Artificial Intelligence,
Recently a number of algorithmic results have appeared
which show the tractability of Integer Linear
Programming (ILP) instances under strong restrictions
on variable domains and/or coefficients
(AAAI 2016, AAAI 2017, IJCAI 2017). In this paper,
we target ILPs where neither the variable domains
nor the coefficients are restricted by a fixed
constant or parameter; instead, we only require that
our instances can be encoded in unary.
We provide new algorithms and lower bounds for
such ILPs by exploiting the structure of their variable
interactions, represented as a graph. Our
first set of results focuses on solving ILP instances
through the use of a graph parameter
called clique-width, which can be seen as an extension
of treewidth which also captures wellstructured
dense graphs. In particular, we obtain
a polynomial-time algorithm for instances of
bounded clique-width whose domain and coefficients
are polynomially bounded by the input size,
and we complement this positive result by a number
of algorithmic lower bounds. Afterwards, we
turn our attention to ILPs with acyclic variable interactions.
In this setting, we obtain a complexity
map for the problem with respect to the graph representation
used and restrictions on the encoding.
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.