Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/21091
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Deza, Antoine | - |
dc.contributor.author | Indik, Gabriel | - |
dc.date.accessioned | 2017-02-10T17:58:01Z | - |
dc.date.available | 2017-02-10T17:58:01Z | - |
dc.date.issued | 2006-05 | - |
dc.identifier.uri | http://hdl.handle.net/11375/21091 | - |
dc.description | Title: Polyhedra Computation Under Symmetry, Author: Gabriel Indik, Location: Thode | en_US |
dc.description.abstract | <p>The last 15 years have seen 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 metric polytope associated to the well-known maxcut and multicommodity flow problems, as well as to finite metric spaces. To tackle the huge size of the problem hundreds of trillions of vertices - a parallel or bitwise enumeration algorithm was implemented and run on Shared Hierarchical Academic Research Computing Network (SHARCNET) clusters. Exploiting the high degree of symmetry, we provide for t he first time a description of the highly degenerate metric polytope in dimension 36. The description consists of 1 056 368 orbits and is conjectured to be complete. While the validity of the dominating set conjecture [Laurent-Poljak, 1992] is proven for the overwhelming majority of the known vertices of the metric polytope, we disprove the conjecture by exhibiting counterexamples in dimensions 36 and 45.</p> | en_US |
dc.language.iso | en | en_US |
dc.title | Polyhedra Computation Under Symmetry | en_US |
dc.type | Thesis | en_US |
dc.contributor.department | Computing and Software | en_US |
dc.description.degreetype | Thesis | en_US |
dc.description.degree | Master of Science (MS) | en_US |
Appears in Collections: | Digitized Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Indik_Gabriel_2006_05_master.pdf | Title: Polyhedra Computation Under Symmetry, Author: Gabriel Indik, Location: Thode | 25.57 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.