Downloads: 3

Files in This Item:
File Description SizeFormat 
RIMS1953.pdf101.1 kBAdobe PDFView/Open
Title: A Note on Integrality of Convex Polyhedra Represented by Linear Inequalities with {0,±1}-coefficients
Authors: FUJISHIGE, Satoru
Issue Date: Sep-2021
Publisher: Research Institute for Mathematical Sciences, Kyoto University
Start page: 1
End page: 9
Thesis number: RIMS-1953
Abstract: We consider a polyhedron P represented by linear inequalities with {0, ±1}-coefficients. We show a condition that guarantees existence of an integral vector in P, which also turns out to be an extreme point of P. We reveal how our polyhedral and geometric approach shows the recent interesting integrality results of Murota and Tamura about subdifferentials of integrally convex functions. Their proofs are algebraic, based on the Fourier-Motzkin elimination for the relevant systems of linear inequalities. Our approach provides further insight into subdifferentials of integrally convex functions to fully appreciate the integrality results of Murota and Tamura from a polyhedral and geometric point of view.
URI: http://hdl.handle.net/2433/265429
Related Link: http://www.kurims.kyoto-u.ac.jp/preprint/index.html
Appears in Collections:Research Institute for Mathematical Sciences, preprints

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.