Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 3 of 3 for “"Combinatorial Diameter"”.
-
On The Circuit Diameters of Some Combinatorial Polytopes
The combinatorial diameter of a polytope P is the maximum value of a shortest path between two vertices of P, where the path uses the edges of P only. In contrast to the combinatorial diameter, the circuit diameter of P is defined as the maximum value of a shortest path between two vertices of P, …
-
Polytopes of minimal circuit diameter
… of optimality. This thesis explores the circuit diameter, a generalization of combinatorial diameter using circuits, of certain polytopes, focusing on when the circuit diameter is small and what criteria for small circuit diameter exist. Such classifications of polytopes with small circuit …
-
Polyhedral Diameters and Applications to Optimization
… of steps in the Simplex method, and the circuit-diameter of polyhedra has been studied as a lower bound to the combinatorial diameter of polyhedra. We show that in the circuit-augmentation framework the Greatest Improvement and Dantzig pivot rules are NP-hard, even for 0/1 LPs. On the other hand, …