University of Twente Student Theses

Login

The Rectangle Covering Bound on the Extension Complexity of Small Cut Polytopes

Fokkema, Wouter (2021) The Rectangle Covering Bound on the Extension Complexity of Small Cut Polytopes.

[img] PDF
518kB
Abstract:The extension complexity of small cut polytopes on the complete graph is lower bounded by the rectangle covering bound. An investigation is done to find techniques of computing this number for small instances, using the symmetries of the cut polytope and linear programming formulations. The extension complexity is shown to be maximal for cut polytopes of complete graphs of up to 8 nodes.
Item Type:Essay (Master)
Clients:
Unknown organization, Netherlands
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics MSc (60348)
Link to this item:https://purl.utwente.nl/essays/86112
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page