Source author record

Iskander Aliev

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.OC math.CO math.NT math.MG math.LO

Catalog footprint

Research overview

13works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Distance-sparsity transference for vertices of corner polyhedra

We obtain a transference bound for vertices of corner polyhedra that connects two well-established areas of research: proximity and sparsity of solutions to integer programs. In the knapsack scenario, it gives an exponential (in the size of support of a solution) improvement on previously known proximity estimates. In addition, for general integer linear programs we obtain a resembling result that connects the minimum absolute nonzero entry of an optimal solution with the size of its support.

preprint2020arXiv

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.

preprint2020arXiv

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.

preprint2020arXiv

Optimizing Sparsity over Lattices and Semigroups

Motivated by problems in optimization we study the sparsity of the solutions to systems of linear Diophantine equations and linear integer programs, i.e., the number of non-zero entries of a solution, which is often referred to as the $\ell_0$ -norm. Our main results are improved bounds on the $\ell_0$ -norm of sparse solutions to systems $A x = b$ , where $A \in \mathbb{Z}^{m \times n}$ , $b \in \mathbb{Z}^m$ and $x$ is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In the lattice case and certain scenarios of the semigroup case, we give polynomial time algorithms for computing solutions with $\ell_0$ -norm satisfying the obtained bounds.

preprint2016arXiv

Integrality Gaps of Integer Knapsack Problems

We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a "typical" knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario.

preprint2015arXiv

A Quantitative Doignon-Bell-Scarf Theorem

The famous Doignon-Bell-Scarf Theorem is a Helly-type result about the existence of integer solutions on systems of linear inequalities. The purpose of this paper is to present the following quantitative generalization: Given an integer $k$ , we prove that there exists a constant $c(n,k)$ , depending only on the dimension $n$ and $k$ , such that if a polyhedron ${x: Ax \leq b}$ contains exactly k integer solutions, then there exists a subset of the rows, of cardinality no more than $c(n,k)$ , defining a polyhedron that contains exactly the same $k$ integer points. In this case $c(n,0) = 2^n$ is the original case of Doignon-Bell-Scarf for infeasible systems of inequalities. We work on both upper and lower bounds for the constant $c(n,k)$ and discuss some consequences, including a Clarkson-style algorithm to find the $l$ -th best solution of an integer program with respect to the ordering induced by the objective function.

preprint2015arXiv

On the lattice programming gap of the group problems

We show that computing the lattice programming gap of the group problems is NP-hard when the dimension is a part of input. We also obtain lower and upper bounds for the gap in terms of the cost vector and the determinant of the lattice.

preprint2015arXiv

Parametric Polyhedra with at least $k$ Lattice Points: Their Semigroup Structure and the k-Frobenius Problem

Given an integral $d \times n$ matrix $A$ , the well-studied affine semigroup $\mbox{ Sg} (A)=\{ b : Ax=b, \ x \in {\mathbb Z}^n, x \geq 0\}$ can be stratified by the number of lattice points inside the parametric polyhedra $P_A(b)=\{x: Ax=b, x\geq0\}$ . Such families of parametric polyhedra appear in many areas of combinatorics, convex geometry, algebra and number theory. The key themes of this paper are: (1) A structure theory that characterizes precisely the subset $\mbox{ Sg}_{\geq k}(A)$ of all vectors $b \in \mbox{ Sg}(A)$ such that $P_A(b) \cap {\mathbb Z}^n$ has at least $k$ solutions. We demonstrate that this set is finitely generated, it is a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computations. Related results can be derived for those right-hand-side vectors $b$ for which $P_A(b) \cap {\mathbb Z}^n$ has exactly $k$ solutions or fewer than $k$ solutions. (2) A computational complexity theory. We show that, when $n$ , $k$ are fixed natural numbers, one can compute in polynomial time an encoding of $\mbox{ Sg}_{\geq k}(A)$ as a multivariate generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors of bounded norm that have at least $k$ solutions. (3) Applications and computation for the $k$ -Frobenius numbers. Using Generating functions we prove that for fixed $n,k$ the $k$ -Frobenius number can be computed in polynomial time. This generalizes a well-known result for $k=1$ by R. Kannan. Using some adaptation of dynamic programming we show some practical computations of $k$ -Frobenius numbers and their relatives.

preprint2014arXiv

Bounding the Number of Maximal Torsion Cosets on Subvarieties of Algebraic Tori

We obtain bounds on the number of maximal torsion cosets for algebraic subvarieties of n-tori, defined over the rationals, using model theoretic methods.

preprint2014arXiv

Iterated Chvatal-Gomory Cuts and the Geometry of Numbers

Chvatal-Gomory cutting planes (CG-cuts for short) are a fundamental tool in Integer Programming. Given any single CG-cut, one can derive an entire family of CG-cuts, by `iterating' its multiplier vector modulo one. This leads naturally to two questions: first, which iterates correspond to the strongest cuts, and, second, can we find such strong cuts efficiently? We answer the first question empirically, by showing that one specific approach for selecting the iterate tends to perform much better than several others. The approach essentially consists in solving a nonlinear optimization problem over a special lattice associated with the CG-cut. We then provide a partial answer to the second question, by presenting a polynomial-time algorithm that yields an iterate that is strong in a certain well-defined sense. The algorithm is based on results from the algorithmic geometry of numbers.

preprint2012arXiv

Integer Points in Knapsack Polytopes and s-covering Radius

Given an integer matrix A satisfying certain regularity assumptions, we consider for a positive integer s the set F_s(A) of all integer vectors b such that the associated knapsack polytope P(A,b)={x: Ax=b, x non-negative} contains at least s integer points. In this paper we investigate the structure of the set F_s(A) sing the concept of s-covering radius. In particular, in a special case we prove an optimal lower bound for the s-Frobenius number.

preprint2011arXiv

Generalized Frobenius numbers: Bounds and average behavior

We produce new upper and lower bounds for the s-Frobenius number by relating it to the so called s-covering radius of a certain convex body with respect to a certain lattice; this generalizes a well-known theorem of R. Kannan for the classical Frobenius number. Using these bounds, we obtain results on the average behavior of the s-Frobenius number, extending analogous recent investigations for the classical Frobenius number by a variety of authors. We also derive bounds on the s-covering radius, an interesting geometric quantity in its own right.

preprint2011arXiv

LLL-reduction for Integer Knapsacks

Given an integer mxn matrix A satisfying certain regularity assumptions, a well-known integer programming problem asks to find an integer point in the associated knapsack polytope P(A, b)={x: A x= b, x>=0} or determine that no such point exists. We obtain a LLL-based polynomial time algorithm that solves the problem subject to a constraint on the location of the vector b.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Iskander Aliev

Research overview

Is this your work?

13 publications

Distance-sparsity transference for vertices of corner polyhedra

On polynomial-time solvable linear Diophantine problems

On the volume of hyperplane sections of a d-cube

Optimizing Sparsity over Lattices and Semigroups

Integrality Gaps of Integer Knapsack Problems

A Quantitative Doignon-Bell-Scarf Theorem

On the lattice programming gap of the group problems

Parametric Polyhedra with at least $k$ Lattice Points: Their Semigroup Structure and the k-Frobenius Problem

Bounding the Number of Maximal Torsion Cosets on Subvarieties of Algebraic Tori

Iterated Chvatal-Gomory Cuts and the Geometry of Numbers

Integer Points in Knapsack Polytopes and s-covering Radius

Generalized Frobenius numbers: Bounds and average behavior

LLL-reduction for Integer Knapsacks

See the researcher in context

Building this map preview

Iskander Aliev

Research overview

Is this your work?

13 publications

Distance-sparsity transference for vertices of corner polyhedra

On polynomial-time solvable linear Diophantine problems

On the volume of hyperplane sections of a d-cube

Optimizing Sparsity over Lattices and Semigroups

Integrality Gaps of Integer Knapsack Problems

A Quantitative Doignon-Bell-Scarf Theorem

On the lattice programming gap of the group problems

Parametric Polyhedra with at least kkk Lattice Points: Their Semigroup Structure and the k-Frobenius Problem

Bounding the Number of Maximal Torsion Cosets on Subvarieties of Algebraic Tori

Iterated Chvatal-Gomory Cuts and the Geometry of Numbers

Integer Points in Knapsack Polytopes and s-covering Radius

Generalized Frobenius numbers: Bounds and average behavior

LLL-reduction for Integer Knapsacks

See the researcher in context

Building this map preview

Parametric Polyhedra with at least $k$ Lattice Points: Their Semigroup Structure and the k-Frobenius Problem