On the membership problem for the elementary closure of a polyhedron

Authors
Eisenbrand, F
Citation
F. Eisenbrand, On the membership problem for the elementary closure of a polyhedron, COMBINATORI, 19(2), 1999, pp. 297-300
Citations number
5
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
19
Issue
2
Year of publication
1999
Pages
297 - 300
Database
ISI
SICI code
0209-9683(1999)19:2<297:OTMPFT>2.0.ZU;2-T
Abstract
The problem: Given an integral matrix A, an integral vector b and some rati onal vector (x) over cap, decide whether (x) over cap is outside the elemen tary closure {x is an element of R-n\Ax less than or equal to b}', is NP-co mplete. This result is achieved by an extension of a result by Caprara and Fischetti.