Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/21784
Title: | Face Lattice Computation under Symmetry |
Authors: | Li, Johnathan |
Advisor: | Deza, Antoine |
Department: | Computational Engineering and Science |
Keywords: | face lattice;computation;symmetry;algorithm |
Publication Date: | Aug-2008 |
Abstract: | The last 15 years have seen a significant progress in the development of general purpose algorithms and software for polyhedral computation. Many polytopes of practical interest have enormous output complexity and are often highly degenerate, posing severe difficulties for known general purpose algorithms. They are, however, highly structured and attention has turned to exploiting this structure, particularly symmetry. We focus on polytopes arising from combinatorial optimization problems. In particular, we study the face lattice of the metric polytope associated with the well-known maxcut and multicommodity flow problems, as well as with finite metric spaces. Exploiting the high degree of symmetry, we provide the first complete orbitwise description of the higher layers of the face lattice of the metric polytope for any dimension. Further computational and combinatorial issues are presented. |
URI: | http://hdl.handle.net/11375/21784 |
Appears in Collections: | Digitized Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Li_Jonathan_2008Aug_Masters.pdf | 2.13 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.