Iskander Aliev
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Iskander Aliev has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Martin Henk
Institut für Mathematik, Technische Universität Berlin, Berlin, Germany
7 shared publications - Jesus A. De Loera
Department of Mathematics, University of California, Davis, USA
5 shared publications - Timm Oertel
School of Mathematics Cardiff University United Kingdom
5 shared publications - Marcel Celaya
Cardiff University
3 shared publications - Quentin Louveaux
University of Liège
3 shared publications - Abdullah Alasmari
Mathematics Institute, Cardiff University, Cardiff, Wales, UK
1 shared publication
Latest Publications
- Open Access
- 31 January 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 216 (1-2) , 29-48
Sparsity and proximity transference in integer programming
We obtain new transference bounds that connect the additive integrality gap and sparsity of solutions for integer linear programs. Specifically, we consider the integer programs $$\min \{{\varvec{c}}\cdot {\varvec{x}}: {\varvec{x}}\in P\cap \mathbb {Z}^n\}$$ , where $$P=\{{\varvec{x}}\in \mathbb {R}^n: \varvec{A}{\varvec{x}}={\varvec{b}}, {\varvec{x}}\ge {\varvec{0}}\}$$ is a polyhedron in the standard form determined by an integer $$m\times n$$ matrix $$\varvec{A}$$ and an integer vector $${\varvec{b}}$$ . The main result of the paper gives an upper bound for the integrality gap that drops exponentially in the size of the support of the optimal solutions corresponding to the vertices of the integer hull of P . Additionally, we obtain a new proximity estimate for the $$\ell _2$$ -distance from a vertex of P to its nearest integer point in P . We also strengthen previously known bounds for the integer Carathéodory rank, a key sparsity characteristic which estimates the minimum size of the support of an integer point in P in terms of the matrix $$\varvec{A}$$ . The proofs make use of the results from the geometry of numbers and convex geometry.- 31 January 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 216 (1-2) , 29-48
Open AccessSparsity and proximity transference in integer programming
We obtain new transference bounds that connect the additive integrality gap and sparsity of solutions for integer linear programs. Specifically, we consider the integer programs $$\min \{{\varvec{c}}\cdot {\varvec{x}}: {\varvec{x}}\in P\cap \mathbb {Z}^n\}$$ , where $$P=\{{\varvec{x}}\in \mathbb {R}^n: \varvec{A}{\varvec{x}}={\varvec{b}}, {\varvec{x}}\ge {\varvec{0}}\}$$ is a polyhedron in the standard form determined by an integer $$m\times n$$ matrix $$\varvec{A}$$ and an integer vector $${\varvec{b}}$$ . The main result of the paper gives an upper bound for the integrality gap that drops exponentially in the size of the support of the optimal solutions corresponding to the vertices of the integer hull of P . Additionally, we obtain a new proximity estimate for the $$\ell _2$$ -distance from a vertex of P to its nearest integer point in P . We also strengthen previously known bounds for the integer Carathéodory rank, a key sparsity characteristic which estimates the minimum size of the support of an integer point in P in terms of the matrix $$\varvec{A}$$ . The proofs make use of the results from the geometry of numbers and convex geometry. - 22 May 2024
- Published by Springer Nature
- p. 1-13
Sparsity and Integrality Gap Transference Bounds for Integer Programs
- 22 May 2024
- Published by Springer Nature
- p. 1-13
Sparsity and Integrality Gap Transference Bounds for Integer Programs
- Open Access
Sparsity and integrality gap transference bounds for integer programs
We obtain new transference bounds that connect two active areas of research: proximity and sparsity of solutions to integer programs. Specifically, we study the additive integrality gap of the integer linear programs min{cx: x in P, x integer}, where P={x: Ax=b, x nonnegative} is a polyhedron in the standard form determined by an integer mxn matrix A and an integer vector b. The main result of the paper shows that the integrality gap drops exponentially in the size of support of the optimal solutions that correspond to the vertices of the integer hull of the polyhedron P. Additionally, we obtain a new proximity bound that estimates the distance from any point of P to its nearest integer point in P. The proofs make use of the results from the geometry of numbers and convex geometry.
Open AccessSparsity and integrality gap transference bounds for integer programs
We obtain new transference bounds that connect two active areas of research: proximity and sparsity of solutions to integer programs. Specifically, we study the additive integrality gap of the integer linear programs min{cx: x in P, x integer}, where P={x: Ax=b, x nonnegative} is a polyhedron in the standard form determined by an integer mxn matrix A and an integer vector b. The main result of the paper shows that the integrality gap drops exponentially in the size of support of the optimal solutions that correspond to the vertices of the integer hull of the polyhedron P. Additionally, we obtain a new proximity bound that estimates the distance from any point of P to its nearest integer point in P. The proofs make use of the results from the geometry of numbers and convex geometry.
- Open Access
- 18 May 2023
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Communications in Mathematics
- Vol. ume 31 (20
Minkowski's successive minima in convex and discrete geometry
In this short survey we want to present some of the impact of Minkowski's successive minima within Convex and Discrete Geometry. Originally related to the volume of an $o$-symmetric convex body, we point out relations of the successive minima to other functionals, as e.g., the lattice point enumerator or the intrinsic volumes and we present some old and new conjectures about them. Additionally, we discuss an application of successive minima to a version of Siegel's lemma.
- 18 May 2023
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Communications in Mathematics
- Vol. ume 31 (20
Open AccessMinkowski's successive minima in convex and discrete geometry
In this short survey we want to present some of the impact of Minkowski's successive minima within Convex and Discrete Geometry. Originally related to the volume of an $o$-symmetric convex body, we point out relations of the successive minima to other functionals, as e.g., the lattice point enumerator or the intrinsic volumes and we present some old and new conjectures about them. Additionally, we discuss an application of successive minima to a version of Siegel's lemma.
- Open Access
- 13 September 2022
- Published by Springer Nature in Optimization Letters
- Vol. 17 (3) , 739-751
On unique recovery of finite-valued integer signals and admissible lattices of sparse hypercubes
The paper considers the problem of unique recovery of sparse finite-valued integer signals using a single linear integer measurement. For l-sparse signals in $${\mathbb {Z}}^n$$ , $$2l<n$$ , with absolute entries bounded by r, we construct an $$1\times n$$ measurement matrix with maximum absolute entry $$\Delta =O(r^{2l-1})$$ . Here the implicit constant depends on l and n and the exponent $$2l-1$$ is optimal. Additionally, we show that, in the above setting, a single measurement can be replaced by several measurements with absolute entries sub-linear in $$\Delta$$ . The proofs make use of results on admissible $$(n-1)$$ -dimensional integer lattices for m-sparse n-cubes that are of independent interest.- 13 September 2022
- Published by Springer Nature in Optimization Letters
- Vol. 17 (3) , 739-751
Open AccessOn unique recovery of finite-valued integer signals and admissible lattices of sparse hypercubes
The paper considers the problem of unique recovery of sparse finite-valued integer signals using a single linear integer measurement. For l-sparse signals in $${\mathbb {Z}}^n$$ , $$2l<n$$ , with absolute entries bounded by r, we construct an $$1\times n$$ measurement matrix with maximum absolute entry $$\Delta =O(r^{2l-1})$$ . Here the implicit constant depends on l and n and the exponent $$2l-1$$ is optimal. Additionally, we show that, in the above setting, a single measurement can be replaced by several measurements with absolute entries sub-linear in $$\Delta$$ . The proofs make use of results on admissible $$(n-1)$$ -dimensional integer lattices for m-sparse n-cubes that are of independent interest. - Open Access
- 4 May 2021
- Published by Springer Nature in Mathematical Programming
- Vol. 192 (1-2) , 519-546
Sparse representation of vectors in lattices and semigroups
We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the $$\ell _0$$ -norm of the vector. Our main results are new improved bounds on the minimal $$\ell _0$$ -norm of solutions to systems $$A\varvec{x}=\varvec{b}$$ , where $$A\in \mathbb {Z}^{m\times n}$$ , $${\varvec{b}}\in \mathbb {Z}^m$$ and $$\varvec{x}$$ is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with $$\ell _0$$ -norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over $$\mathbb {R}$$ , to other subdomains such as $$\mathbb {Z}$$ . We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.- 4 May 2021
- Published by Springer Nature in Mathematical Programming
- Vol. 192 (1-2) , 519-546
Open AccessSparse representation of vectors in lattices and semigroups
We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the $$\ell _0$$ -norm of the vector. Our main results are new improved bounds on the minimal $$\ell _0$$ -norm of solutions to systems $$A\varvec{x}=\varvec{b}$$ , where $$A\in \mathbb {Z}^{m\times n}$$ , $${\varvec{b}}\in \mathbb {Z}^m$$ and $$\varvec{x}$$ is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with $$\ell _0$$ -norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over $$\mathbb {R}$$ , to other subdomains such as $$\mathbb {Z}$$ . We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables. - Open Access
On the volume of hyperplane sections of a d-cube
We obtain an optimal upper bound for the normalised volume of a hyperplane section of an origin-symmetric d-dimensional cube. This confirms a conjecture posed by Imre Barany and Peter Frankl.
Open AccessOn the volume of hyperplane sections of a d-cube
We obtain an optimal upper bound for the normalised volume of a hyperplane section of an origin-symmetric d-dimensional cube. This confirms a conjecture posed by Imre Barany and Peter Frankl.
- 30 June 2020
- Published by Springer Nature in Acta Mathematica Hungarica
- Vol. 163 (2) , 547-551
On the volume of hyperplane sections of a d-cube
- 30 June 2020
- Published by Springer Nature in Acta Mathematica Hungarica
- Vol. 163 (2) , 547-551
On the volume of hyperplane sections of a d-cube
- Open Access
On polynomial-time solvable linear Diophantine problems
We obtain a polynomial-time algorithm that, given input (A, b), where A=(B|N) is an integer mxn matrix, m<n, with nonsingular mxm submatrix B and b is an m-dimensional integer vector, finds a nonnegative integer solution to the system Ax=b or determines that no such solution exists, provided that b is located sufficiently "deep" in the cone generated by the columns of B. This result improves on some of the previously known conditions that guarantee polynomial-time solvability of linear Diophantine problems.
Open AccessOn polynomial-time solvable linear Diophantine problems
We obtain a polynomial-time algorithm that, given input (A, b), where A=(B|N) is an integer mxn matrix, m<n, with nonsingular mxm submatrix B and b is an m-dimensional integer vector, finds a nonnegative integer solution to the system Ax=b or determines that no such solution exists, provided that b is located sufficiently "deep" in the cone generated by the columns of B. This result improves on some of the previously known conditions that guarantee polynomial-time solvability of linear Diophantine problems.
- Open Access
- 2 April 2019
- Published by Springer Nature in Mathematical Programming
- Vol. 182 (1-2) , 175-198
Distances to lattice points in knapsack polyhedra
- 2 April 2019
- Published by Springer Nature in Mathematical Programming
- Vol. 182 (1-2) , 175-198
Open AccessDistances to lattice points in knapsack polyhedra