Published in:
An integer polyhedron $P \subseteq \Rset^n$ has the linking property if for any $f \in \Zset^n$ and $g \in \Zset^n$ with $f \leq g$, $P$ has an integer point between $f$ and $g$ if and only if it has both an integer point above $f$ and an integer point below $g$. We prove that an integer polyhedron in the hyperplane $\sum_{j=1}^n x_j=\beta$ is a base polyhedron if and only if it has the linking property. The result implies that an integer polyhedron has the strong linking property, as defined in [A. Frank, T. Király, A survey on covering supermodular functions, 2009], if and only if it is a generalized polymatroid.
Bibtex entry:
AUTHOR | = | {Kir{\'a}ly, Tam{\'a}s}, |
TITLE | = | {Base polyhedra and the linking property}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2016}, |
NUMBER | = | {TR-2016-06} |