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. Conferences, Workshops, Symposiums, and Seminars
  4. Testing additive integrality gaps
 
conference paper

Testing additive integrality gaps

Eisenbrand, Friedrich  
•
Hähnle, Nicolai  
•
Pálvölgyi, Dömötör  
Show more
2010
21st ACM-SIAM Symposium on Discrete Algorithms (SODA10)
21st ACM-SIAM Symposium on Discrete Algorithms

We consider the problem of testing whether the maximum integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomial time if the number of constraints is fixed. It turns out that this generalization is NP-hard even if the number of constraints is fixed. However, if, in addition, the objective is the all-one vector, then one can test in polynomial time whether the additive gap is bounded by a constant.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

eisenbrandf-gaps.pdf

Access type

openaccess

Size

153.75 KB

Format

Adobe PDF

Checksum (MD5)

022c68bd6c71ab883653260d48e1d9ff

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