Parameterised integer programming, integer cones, and related problems / Gennady Shmonin. 2007
Inhalt
- Introduction
- Preliminaries
- Basic definitions and notation
- Matrices and linear algebra
- Algorithms and complexity
- Polyhedra and linear programming
- The ellipsoid method
- Integer programming and lattices
- Integral Vectors in a Parameterised Polyhedron
- Integer programming in fixed dimension
- Lattice width of a parameterised polyhedron
- Integer projections
- Structural theorem
- Application of the Structural Theorem
- Integer Programs in Standard Form
- Cutting Stock Problem
- Introduction
- Integer programming formulation
- Residual instances and small items
- Integer programming gaps
- Polynomial-size integer programs
- Conclusions and Open Questions