  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 circuits, that is a superset of the edges of a polytope. We show that in
the circuit-augmentation framework the greatest-improvement and Dantzig pivot
rules are NP-hard, already for 0/1-LPs. Differently, the steepest-descent 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.
  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.
Extending prior results, we show that for any polyhedron $P$ the
circuit-diameter is bounded by a polynomial in the input bit-size of $P$. This
is in contrast with the best bounds for the combinatorial diameter of
polyhedra.
  Interestingly, we 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$ polytopes, a monotone path of strongly-polynomial length
can be constructed using steepest improving edges.
