Caratheodory bounds for integer cones

Friedrich Eisenbrand, Gennady Shmonin
2006
Article

Résumé

We provide analogues of Caratheodory's theorem for integer cones and apply our bounds to integer programming and to the cutting stock problem. In particular, we provide an NP certificate for the latter, whose existence has not been known so far. © 2005 Elsevier B.V. All rights reserved.

Source officielle

https://infoscience.epfl.ch/record/121640?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Caratheodory bounds for integer cones

Results on Sparse Integer Programming and Geometric Independent Sets

The double exponential runtime is tight for 2-stage stochastic ILPs

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Results on Sparse Integer Programming and Geometric Independent Sets

The double exponential runtime is tight for 2-stage stochastic ILPs