\(k\)-integrality, an extension of total unimodularity
type: Item
instance of: scholarly article
title: \(k\)-integrality, an extension of total unimodularity
zbMATH Open document ID: 0792.90049
DOI: 10.1016/0167-6377(93)90005-2
author: G. Appa
published in: Operations Research Letters
publication date: 1993-11-01T00:00:00Z
review text: The author considers a matrix \(A\) of integers and a vector \(b\) of integers such that all the elements of \(b\) have a common divisor \(k\). He gives a necessary and sufficient condition for the polyhedron \(P(a,b)\), where \(P(a,b)=\{x\mid x\geq 0,\;Ax\leq b\}\), to have only integral extreme points. These conditions refer to elements of inverse matrices of all bases derived from \(A\), and they are an extension of the classical theory of total unimodularity to \(k\)-integrability. A special version is provided for the case where \(k\) is a prime number. For \(k=2\) applications of this result are shown for the obnoxious facility location problem [see the author and \textit{I. Giannikos}, J. Oper. Res. Soc., to appear] and for ternary covering and packing problems.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90B80
zbMATH DE Number: 438800
zbMATH Keywords: integral extreme points
zbMATH Keywords: total unimodularity
zbMATH Keywords: obnoxious facility location
zbMATH Keywords: ternary covering and packing
reviewed by: Daniela Marinescu
MaRDI profile type: Publication
full work available at URL: 0167-6377(93)90005-2
OpenAlex ID: W2049215495
cites work: Is Linear Programming Necessary for Single Facility Location with Maximin of Rectilinear Distance?
cites work: Establishing the matching polytope
cites work: Characterization of Totally Unimodular Matrices
cites work: On ternary problems
cites work: Q3236252
cites work: An Enhancement of the Drezner-Wesolowsky Algorithm for Single-Facility Location with Maximin of Rectilinear Distance
cites work: An Efficient Computational Procedure for the Rectilinear MAXIMIN Location Problem
cites work: Integral Extreme Points
description: scientific article; zbMATH DE number 438800