On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
From MaRDI portal
Publication:6200377
DOI10.1007/s10898-022-01165-9arXiv2002.01307MaRDI QIDQ6200377
Panos M. Pardalos, Ivan Shumilov, Dmitriy V. Gribanov, Dmitriy S. Malyshev
Publication date: 22 March 2024
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2002.01307
knapsack probleminteger linear programmingsubset-sum problemempty simplexgroup minimization problemsparsity \& proximity bounds
Related Items
Cites Work
- On integer programming with bounded determinants
- The width and integer optimization on simplices with bounded minors of the constraint matrices
- A complexity dichotomy and a new boundary class for the dominating set problem
- Critical hereditary graph classes: a survey
- Linear time algorithms for some separable quadratic programming problems
- A fast and simple algorithm for the money changing problem
- Integer program with bimodular matrix
- The vertices of the knapsack polytope
- Discrepancy of set-systems and matrices
- A geometric inequality with applications to linear forms
- On integer points in polyhedra
- Lattice invariant valuations on rational polytopes
- The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
- FPT-algorithms for some problems related to integer programming
- A note on non-degenerate integer programs with small sub-determinants
- Dynamic programming revisited: Improving knapsack algorithms
- The integrality number of an integer program
- Sparse representation of vectors in lattices and semigroups
- On lattice point counting in \(\varDelta\)-modular polyhedra
- Integer conic function minimization based on the comparison oracle
- Distances to lattice points in knapsack polyhedra
- A polynomial algorithm for minimizing discrete convic functions in fixed dimension
- Improving proximity bounds using sparsity
- Sparsity of integer solutions in the average case
- FPT-algorithm for computing the width of a simplex given by a convex hull
- The computational complexity of three graph problems for instances with bounded minors of constraint matrices
- Geometric random edge
- On the complexity of quasiconvex integer minimization problem
- Boundary graph classes for some maximum induced subgraph problems
- Effective lattice point counting in rational convex polytopes
- Integer programming in parameterized complexity: five miniatures
- Clustered Integer 3SUM via Additive Combinatorics
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Integer Programming with a Fixed Number of Variables
- Bounds on Positive Integral Solutions of Linear Diophantine Equations II
- On the Power of Linear Dependencies
- Six Standard Deviations Suffice
- Sensitivity theorems in integer linear programming
- Polynomial algorithms in linear programming
- On the complexity of integer programming
- Bounds on Positive Integral Solutions of Linear Diophantine Equations
- Faster All-Pairs Shortest Paths via Circuit Complexity
- The Support of Integer Optimal Solutions
- Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
- A strongly polynomial algorithm for bimodular integer linear programming
- Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
- The Distributions of Functions Related to Parametric Integer Optimization
- Distance-Sparsity Transference for Vertices of Corner Polyhedra
- Classes of graphs critical for the edge list-ranking problem
- The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
- Critical elements in combinatorially closed families of graph classes
- ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
- On largest volume simplices and sub-determinants
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- The maximum numbers of faces of a convex polytope
- On sub-determinants and the diameter of polyhedra
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item