The Support of Integer Optimal Solutions

2017/12/24 by Iskander Aliev, Aliev, Iskander, Jesus De Loera +7 · 2 citations
Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #math.OC

paper · pdf · doi:10.48550/arxiv.1712.08923

arxiv created 2017/12/24 · arxiv updated 2017/12/27

Abstract

The support of a vector is the number of nonzero-components. We show that given an integral m× n matrix A, the integer linear optimization problem max\\boldsymbolc^T\boldsymbolx : A\boldsymbolx = \boldsymbolb, \boldsymbolx≥\boldsymbol0, \boldsymbolx∈ℤⁿ\ has an optimal solution whose support is bounded by 2m log (2 √(m) ‖ A ‖_∞), where ‖ A ‖_∞ is the largest absolute value of an entry of A. Compared to previous bounds, the one presented here is independent on the objective function. We furthermore provide a nearly matching asymptotic lower bound on the support of optimal solutions.

Cited by

• The Support of Bin Packing is Exponential
• A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm
• Semigroups of Integer Points in Convex Cones

Related

• New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
• On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
• Improving the Cook et al. Proximity Bound Given Integral Valued Constraints
• New Bounds for the Vertices of the Integer Hull
• Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma