Affordable Access

Access to the full text

FPT-algorithms for some problems related to integer programming

Authors
  • Gribanov, D. V.1, 2
  • Malyshev, D. S.2
  • Pardalos, P. M.2, 3
  • Veselov, S. I.1
  • 1 Lobachevsky State University of Nizhny Novgorod, 23 Gagarina Avenue, Nizhny Novgorod, 603950, Russian Federation , Nizhny Novgorod (Russia)
  • 2 National Research University Higher School of Economics, 25/12 Bolshaja Pecherskaja Ulitsa, Nizhny Novgorod, 603155, Russian Federation , Nizhny Novgorod (Russia)
  • 3 University of Florida, 401 Weil Hall, Gainesville, FL, 326116595, USA , Gainesville (United States)
Type
Published Article
Journal
Journal of Combinatorial Optimization
Publisher
Springer-Verlag
Publication Date
Feb 17, 2018
Volume
35
Issue
4
Pages
1128–1146
Identifiers
DOI: 10.1007/s10878-018-0264-z
Source
Springer Nature
Keywords
License
Yellow

Abstract

In this paper, we present fixed-parameter tractable algorithms for special cases of the shortest lattice vector, integer linear programming, and simplex width computation problems, when matrices included in the problems’ formulations are near square. The parameter is the maximum absolute value of the rank minors in the corresponding matrices. Additionally, we present fixed-parameter tractable algorithms with respect to the same parameter for the problems, when the matrices have no singular rank submatrices.

Report this publication

Statistics

Seen <100 times