<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T13:14:29Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/18705" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/18705</identifier><datestamp>2025-03-26T23:36:31Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Sanita, Laura</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="6d05c754-5e97-4ceb-85bf-c11882f47787" confidence="600">Kafer, Sean</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2022-09-01T19:18:45Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2022-09-01T19:18:45Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2022-09-01</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2022-08-28</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/18705</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The Simplex method is the most popular algorithm for solving linear programs (LPs). Geometrically, it moves from an initial vertex solution to an improving neighboring one, selected according to a pivot rule. Despite decades of study, it is still not known whether there exists a pivot rule that makes the Simplex method run in polynomial time. &#xd;
&#xd;
Circuit-augmentation algorithms are generalizations of the Simplex method, where in each step one is allowed to move along a fixed set of directions, called the circuits, that is a superset of the edges of a polytope. The number of circuit augmentations has been of interest as a proxy for the number 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, the Steepest Descent&#xd;
pivot rule can be carried out in polynomial time in the 0/1 setting, and the number of circuit augmentations required to reach an optimal solution according to this rule is strongly-polynomial for 0/1 LPs. We introduce a new rule in the circuit-augmentation&#xd;
framework which we call Asymmetric Steepest Descent. We show both that it can be computed in polynomial time and that it reaches an optimal solution of an LP in a polynomial number of augmentations. It was not previously known that such a rule was possible. We further show a weakly-polynomial bound on the circuit diameter of rational polyhedra.&#xd;
&#xd;
We next show that the circuit-augmentation framework can be exploited to make novel conclusions about the classical Simplex method itself: In particular, as a byproduct of our circuit results, we prove that (i) computing the shortest (monotone) path to an optimal solution on the 1-skeleton of a polytope is NP-hard, and hard to approximate within a factor better than 2, and (ii) for 0/1-LPs (i.e., those whose vertex solutions are in {0, 1}^n), a monotone path of strongly-polynomial length can be constructed using steepest improving edges.&#xd;
&#xd;
Inspired by this, we further examine the lengths of other monotone paths generated by some local decision rules – which we call edge rules – including two modifications of the classical Shadow Vertex pivot rule. We leverage the techniques we use for analyzing edge rules to devise pivot rules for the Simplex method on 0/1-LPs that generate the same monotone paths as their edge rule counterparts. In particular, this shows that there exist pivot rules for the Simplex method on 0/1 LPs that reach an optimal solution by performing only a polynomial number of non-degenerate pivots, answering an open question in the literature.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">linear programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">combinatorial optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Simplex</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">circuit diameter</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">combinatorial diameter</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">monotone diameter</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Polyhedral Diameters and Applications to Optimization</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms" lang="en">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Sanita, Laura</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>