Extended formulations for combinatorial polytopes

Kanstantsin Pashkovich

Digitalen Hochschulbibliothek Sachsen-Anhalt (Universitäts- und Landesbibliothek Sachsen-Anhalt) · 2012 · 39 citations · 45 references

DOIFull text

Open access

Concepts

Abstract

Typically polytopes arising from real world problems have a lot of facets.In some cases even no linear descriptions for them are known.On the other hand many of these polytopes can be described much nicer and with less facets using extended formulations, i.e. as a projection of simpler higher dimensional polytopes.The presented work studies extended formulations for polytopes: the possibilities to construct extended formulations and limitations of them.

References

45