|
|||||
|
|
Carathéodory bounds for integer cones |
|
| Authors: | Friedrich Eisenbrand Gennady Shmonin |
| Institution: | Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany |
| Abstract: | We provide analogues of Carathéodory'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. |
| Keywords: | Carathé odory's theorem Integer cone Integer programming Cutting stock Bin packing |
| 本文献已被 ScienceDirect 等数据库收录！ | |