FPT-algorithms for some problems related to integer programming
From MaRDI portal
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.
Recommendations
Cites work
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A new polynomial-time algorithm for linear programming
- A note on non-degenerate integer programs with small sub-determinants
- A sieve algorithm for the shortest lattice vector problem
- A strongly polynomial algorithm for bimodular integer linear programming
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Algorithms for the shortest and closest lattice vector problems
- Covering cubes and the closest vector problem
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- Factoring polynomials with rational coefficients
- Geometric random edge
- scientific article; zbMATH DE number 3859248 (Why is no real title available?)
- scientific article; zbMATH DE number 3987367 (Why is no real title available?)
- scientific article; zbMATH DE number 44906 (Why is no real title available?)
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 1254301 (Why is no real title available?)
- scientific article; zbMATH DE number 1254302 (Why is no real title available?)
- scientific article; zbMATH DE number 1256724 (Why is no real title available?)
- scientific article; zbMATH DE number 1342145 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 3333393 (Why is no real title available?)
- scientific article; zbMATH DE number 958053 (Why is no real title available?)
- Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
- Integer program with bimodular matrix
- Integer Programming with a Fixed Number of Variables
- Minkowski's Convex Body Theorem and Integer Programming
- On integer programming with bounded determinants
- ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
- Parameterized algorithms
- Polynomial algorithms in linear programming
- Sampling methods for shortest vectors, closest vectors and successive minima
- Sensitivity theorems in integer linear programming
- Solving the stable set problem in terms of the odd cycle packing number
- The computational complexity of three graph problems for instances with bounded minors of constraint matrices
- The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
- The width and integer optimization on simplices with bounded minors of the constraint matrices
Cited in
(8)- An FPTAS for the -modular multidimensional knapsack problem
- On lattice point counting in -modular polyhedra
- FPT-algorithm for computing the width of a simplex given by a convex hull
- Sparse integer programming is FPT
- Enumeration and unimodular equivalence of empty delta-modular simplices
- Structured ( ,+)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
- On -modular integer linear problems in the canonical form and equivalent problems
- On the size of integer programs with bounded non-vanishing subdeterminants
This page was built for publication: FPT-algorithms for some problems related to integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1752617)
