A note on non-degenerate integer programs with small sub-determinants

Artmann, S., Eisenbrand, F., Glanzer, C., Oertel, T. ORCID: https://orcid.org/0000-0001-5720-8978, Vempala, S. and Weismantel, R. 2016. A note on non-degenerate integer programs with small sub-determinants. Operations Research Letters 44 (5) , pp. 635-639. 10.1016/j.orl.2016.07.004

Full text not available from this repository.

Abstract

The intention of this note is two-fold. First, we study integer optimization problems in standard form defined by A∈Zm×nA∈Zm×n and find an algorithm to solve such problems in polynomial-time provided that both the largest absolute value of an entry in AA and mm are constant. Then, this is applied to solve integer programs in inequality form in polynomial-time, where the absolute values of all maximal sub-determinants of AA lie between 11 and a constant.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Uncontrolled Keywords:	Integer programming; Restricted determinants; Linear programming
Publisher:	Elsevier
ISSN:	0167-6377
Date of First Compliant Deposit:	2 August 2016
Date of Acceptance:	5 July 2016
Last Modified:	01 Nov 2022 11:00
URI:	https://orca.cardiff.ac.uk/id/eprint/93545

Citation Data

Cited 19 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item