Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/27285
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Deza, Antoine | - |
dc.contributor.author | Suarez, Carlos | - |
dc.date.accessioned | 2022-01-19T21:01:44Z | - |
dc.date.available | 2022-01-19T21:01:44Z | - |
dc.date.issued | 2021 | - |
dc.identifier.uri | http://hdl.handle.net/11375/27285 | - |
dc.description.abstract | Linear optimization aims at maximizing, or minimizing, a linear objective function over a feasible region defined by a finite number of linear constrains. For several well-studied problems such as maxcut, all the vertices of the feasible region are integral, that is, with integer-valued coordinates. The diameter of the feasible region is the diameter of the edge-graph formed by the vertices and the edges of the feasible region. This diameter is a lower bound for the worst-case behaviour for the widely used pivot-based simplex methods to solve linear optimization instances. A lattice (d,k)-polytope is the convex hull of a set of points whose coordinates are integer ranging from 0 to k. This dissertation provides new insights into the determination of the largest possible diameter δ(d,k) over all possible lattice (d,k)-polytopes. An enhanced algorithm to determine δ(d,k) is introduced to compute previously intractable instances. The key improvements are achieved by introducing a novel branching that exploits convexity and combinatorial properties, and by using a linear optimization formulation to significantly reduce the search space. In particular we determine the value for δ(3,7). | en_US |
dc.language.iso | en | en_US |
dc.subject | polytopes | en_US |
dc.subject | lattices | en_US |
dc.subject | diameter | en_US |
dc.subject | optimization | en_US |
dc.title | Discrete Geometry and Optimization Approaches for Lattice Polytopes | en_US |
dc.type | Thesis | en_US |
dc.contributor.department | Computing and Software | en_US |
dc.description.degreetype | Thesis | en_US |
dc.description.degree | Doctor of Philosophy (PhD) | en_US |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Suarez_Carlos_A_2021Dic_PhD.pdf | 2.4 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.