Gennady Shmonin | EPFL Graph Search

Testing additive integrality gaps

Friedrich Eisenbrand, Gennady Shmonin, Nicolai Hähnle

We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in ...

Springer Berlin Heidelberg2013

Testing additive integrality gaps

Friedrich Eisenbrand, Doemoetoer Palvoelgyi, Gennady Shmonin, Nicolai Hähnle

We consider the problem of testing whether the maximum integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomi ...

2010

Parametric integer programming in fixed dimension

Friedrich Eisenbrand, Gennady Shmonin

We consider the following problem: Given a rational matrix

A \in \mathbb{Q}^{m \times n}

and a rational polyhedron

Q \subseteq \mathbb{R}^{m+p}

, decide if for all vectors

b \in \mathbb{R}^m

, for which there exists an integral

z \in \mathbb{Z}^p

suc ...

2008