 homogeneity of the potential function. 
In order to establish a performance bound for Algorithm~\ref{alg:mraScaling} we need the following
simple observation.

\begin{observation}\label{obs:decreasingPot}
  Let \(\tilde{x}\) be the last solution in the scaling phase for~\(\mu\). Then
  for any integer feasible solution~\(x\), \(\tilde{x}\) satisfies
  \[
  \frac{c(x - \tilde{x})}{\rho(\tilde{x}, x - \tilde{x})} \leq \mu,
  \]
  i.e., whenever we enter a new scaling phase we have \(c(x - \tilde{x})
  \leq \mu\, n\) for the potential function in
  Lemma~\ref{lem:standardPotential}, which gives an upper bound on the
  remaining gap.
\end{observation}

Moreover let us point out the following property:

\begin{observation}[Geometric scaling never revisits a point]\label{obs:GSnoRevisit}
  A feasible solution~\(x\) in Algorithm~\ref{alg:mraScaling} satisfies
  \(c(x - \tilde{x}) - \mu \cdot \rho(\tilde{x}, x - \tilde{x}) > 0\) or equivalently,
  \[
  cx > c\tilde{x} + \mu \cdot \underbrace{\rho(\tilde{x},x-\tilde{x})}_{\geq 0}.
  \]
  Thus, geometric scaling produces solutions with strictly increasing
  cost with respect to the original objective function~\(c\) and cannot revisit points.
\end{observation}

The crucial advantage of the geometric scaling algorithm is that it
uses the objective function to guide the search and hence we (potentially) obtain a speed-up over standard augmentation. 
For illustration purposes, we depict the behavior of the geometric
scaling algorithm in Figure~\ref{fig:geoFig}.

\begin{figure}
  \centering
  \IfFileExists{graphics/gsExample_n10.pdf}{
     \includegraphics[scale=0.8]{graphics/gsExample_n10.pdf}
  }
 
  {
  \IfFileExists{gsExample_n10.pdf}{
     \includegraphics[scale=0.8]{gsExample_n10.pdf}
  }{}
  }
  \caption{Illustration of the behavior of geometric scaling. The
    picture shows a polytope in \(\mathds{R}^2\).
    Our initial point is the leftmost point and we maximize
    \(c=(1,0)\)
    (i.e., the maximum is the rightmost point). A worst-case
    augmentation oracle might give the point with smallest
    improvement, which is always an adjacent vertex or jump between
    bottom and top. Standard
    augmentation with such a malicious worst-case oracle would now
    force us to visit either each point on the upper or lower
    path. Geometric scaling constructs shortcuts by controlling the
    objective function, leading to significant speed-ups.}
  \label{fig:geoFig}
\end{figure}

 
As with bit scaling and MRA, Algorithm~\ref{alg:mraScaling} also
requires only polynomially many augmentations with respect to
the encoding length. First we bound the number of augmentations required
per scaling phase.

\begin{lemma}[\cite{schulz2002complexity}]\label{lem:updatesPerPhase}
  Let \(P = \set{x \in \mathds{R}^n}{Ax = b,\, l \leq x \leq u}\),
  let \(\rho\) be the potential function from
  Lemma~\ref{lem:standardPotential}, and let \(x^0 \in P \cap \mathds{Z}^n\) be an integer feasible
  solution. Then Algorithm~\ref{alg:mraScaling} computes at most \(4n\) approximate MRA directions between successive updates of \(\mu\).
\end{lemma}
\begin{proof}
  Let \(y^0, y^1,  \dotsc\) be the points in \(P\) visited by the algorithm during the scaling phase for a given~\(\mu\). In particular,
  \(y^0\) is the current solution after the last update of \(\mu\). By Observation~\ref{obs:decreasingPot}, we have
  \[
  \frac{c(x^\star - y^0)}{\rho(y^0,x^\star - y^0)} \leq 2\mu,
  \]
  where \(x^\star\) is an integral optimal solution for the original problem. Now, consider any two
  consecutive iterates \(y^i\) and \(y^{i+1}\). By definition of
  Algorithm~\ref{alg:mraScaling}, the \(c(y^{i+1} - y^i) - \mu \cdot
  \rho(y^i, y^{i+1} - y^i) > 0\) holds. Moreover, as the direction
  \(y^{i+1} - y^i\) is exhaustive, using Lemma~\ref{lem:standardPotential}, we have 
  \begin{align*}
    c(y^{i+1}-y^i) & > \mu \cdot \rho(y^{i},y^{i+1}-y^i)  \geq \frac{\mu}{2}
    \geq \frac{1}{4} \frac{c(x^\star-y^0)}{\rho(y^0,x^\star-y^0)} \geq
    \frac{1}{4n} c(x^\star-y^0),
  \end{align*}
  hence we compute at most \(4n\) approximate directions in each scaling phase.
\end{proof}

It is interesting to observe that in
Lemma~\ref{lem:updatesPerPhase}, in each scaling phase, we recover at
least a~\(\tfrac{1}{4n}\) fraction of the improvement of the optimal direction \(x^\star-y^0\)
from the feasible solution \(y^0\) at the beginning of the phase to the
optimal solution \(x^\star\). This is in contrast to Theorem~\ref{thm:mraAlgo}, where the guaranteed
improvement of \(\tfrac{1}{2n}\) is with respect to two consecutive iterates 
only, i.e., we only guarantee to recover an \(\tfrac{1}{2n}\) fraction of
the improvement of \(x^\star-y^{i-1}\), if we are in iteration \(i\), which is potentially
smaller than the one from direction  \(x^\star-y^0\).

We will now establish a bound on the number of required approximate MRA
directions, which slightly improves the bound in
\cite{schulz2002complexity} by a \(\log n\) factor. The key insight is
that we can combine 
Observation~\ref{obs:GSnoRevisit} with
Observation~\ref{obs:decreasingPot}, to switch from the multiplicative
regime to the additive regime, simply counting the remaining
improvement steps.  

\begin{theorem}[Improved bound for geometric scaling]\label{thm:mraScalingRt}
 Let \(P = \set{x \in \mathds{R}^n}{Ax = b,\, l \leq x \leq u}\),
 let \(\rho\) be the potential function from
 Lemma~\ref{lem:standardPotential}, and let \(x^0 \in P \cap \mathds{Z}^n\) be an integer feasible
 solution. Then Algorithm~\ref{alg:mraScaling} solves the optimization
 problem \(\max \set{cx}{x \in P \cap \mathds{Z}^n}\)
 with at most \(\order{n \log(C (U-L))}\) computations of approximate MRA
 directions.
\end{theorem}

\begin{proof}
  The algorithm initializes with \(\mu = 2 C(U-L)\). Hence after
  \(\ceil{\log(C(U-L))}+1\) updates of~\(\mu\),
  we have \(\mu\leq1\), and by
  Lemma~\ref{lem:updatesPerPhase} have computed at most
  \(4n(\ceil{\log(C(U-L))}+1)\) approximate MRA directions in total. Let \(\tilde{x}\) be
  the last solution computed by the algorithm in these first
  \(\ceil{\log(C(U-L))}+1\) scaling phases.

  We now switch to the additive regime and simply count the number of
  remaining improvements that are possible. As \(\mu\leq1\), Observation~\ref{obs:decreasingPot} implies
  \[
  c(x^\star - \tilde{x}) \leq \mu \cdot \rho(\tilde{x}, x^\star -
  \tilde{