Back to Search
Start Over
FPT-algorithms for some problems related to integer programming
- Publication Year :
- 2017
-
Abstract
- In this paper, we present FPT-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 rank minors of the corresponding matrices. Additionally, we present FPT-algorithms with respect to the same parameter for the problems, when the matrices have no singular rank sub-matrices.<br />arXiv admin note: text overlap with arXiv:1710.00321 From author: some minor corrections has been done
- Subjects :
- FOS: Computer and information sciences
Control and Optimization
Computation
0211 other engineering and technologies
MathematicsofComputing_NUMERICALANALYSIS
0102 computer and information sciences
02 engineering and technology
Computational Complexity (cs.CC)
01 natural sciences
Lattice (order)
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
Computer Science - Data Structures and Algorithms
FOS: Mathematics
Discrete Mathematics and Combinatorics
Data Structures and Algorithms (cs.DS)
Integer programming
Mathematics - Optimization and Control
Mathematics
021103 operations research
Simplex
Applied Mathematics
Block matrix
Computer Science Applications
Computer Science - Computational Complexity
Computational Theory and Mathematics
010201 computation theory & mathematics
Optimization and Control (math.OC)
Theory of computation
Algorithm
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....ab629d8147a93b3b753c16ff93797113