Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-98-2-018

A note on the membership problem for the first elementary closure of a polyhedron

Eisenbrand, Friedrich

MPI-I-98-2-018. November 1998, 3 pages. | Status: distribution forbidden | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
The problem: Given an integral matrix $A$, an
integral vector $b$ and some rational vector $x$, decide whether $x$
is outside the elementary closure $\{ x \in \R^n \mid Ax \leq b
\}'$, is NP-complete. This result is achieved by an
extension of a result by Caprara and Fischetti.
Acknowledgement:
References to related material: