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
- 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?)
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- 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
- 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
- Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
- Integer Programming with a Fixed Number of Variables
- Integer program with bimodular matrix
- Minkowski's Convex Body Theorem and Integer Programming
- ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
- On integer programming with bounded determinants
- 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 Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
- The computational complexity of three graph problems for instances with bounded minors of constraint matrices
- The width and integer optimization on simplices with bounded minors of the constraint matrices
Cited in
(8)- Enumeration and unimodular equivalence of empty delta-modular simplices
- An FPTAS for the -modular multidimensional knapsack problem
- On the size of integer programs with bounded non-vanishing subdeterminants
- Sparse integer programming is FPT
- Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
- On lattice point counting in -modular polyhedra
- FPT-algorithm for computing the width of a simplex given by a convex hull
- On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
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)
