University of Twente Student Theses
As of Friday, 8 August 2025, the current Student Theses repository is no longer available for thesis uploads. A new Student Theses repository will be available starting Friday, 15 August 2025.
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.
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) |
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