Skip to main content
Open Access Publications from the University of California

Department of Mathematics

Faculty bannerUC Davis

The support of integer optimal solutions

  • Author(s): Aliev, I;
  • De Loera, JA;
  • Eisenbrand, F;
  • Oertel, T;
  • Weismantel, R
  • et al.

The support of a vector is the number of nonzero components. We show that given anintegral m×n matrix A, the integer linear optimization problem maxfcT x: Ax = b; x = 0; x 2 Znghas an optimal solution whose support is bounded by 2m log(2pmkAk1), where kAk1 is the largestabsolute value of an entry of A. Compared to previous bounds, the one presented here is independentof the objective function. We furthermore provide a nearly matching asymptotic lower bound on thesupport of optimal solutions.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View