Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. The Support Of Integer Optimal Solutions
 
research article

The Support Of Integer Optimal Solutions

Aliev, I.
•
De Loera, J. A.
•
Eisenbrand, F.  
Show more
January 1, 2018
Siam Journal On Optimization

The support of a vector is the number of nonzero components. We show that given an integral mxn matrix A, the integer linear optimization problem max {c(T) x : Ax = b, x >= 0, x is an element of Z(n)} has an optimal solution whose support is bounded by 2m log(2 root m parallel to Lambda parallel to(infinity)), where parallel to Lambda parallel to(infinity) is the largest absolute value of an entry of A. Compared to previous bounds, the one presented here is independent of the objective function. We furthermore provide a nearly matching asymptotic lower bound on the support of optimal solutions.

  • Details
  • Metrics
Type
research article
DOI
10.1137/17M1162792
Web of Science ID

WOS:000445767000010

Author(s)
Aliev, I.
De Loera, J. A.
Eisenbrand, F.  
Oertel, T.
Weismantel, R.
Date Issued

2018-01-01

Publisher

SIAM PUBLICATIONS

Published in
Siam Journal On Optimization
Volume

28

Issue

3

Start page

2152

End page

2157

Subjects

Mathematics, Applied

•

Mathematics

•

support function

•

sparse solutions

•

integer linear programs

•

caratheodory

•

variables

•

number

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Available on Infoscience
December 13, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/152500
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés