\documentclass[11pt]{article}

\newcommand{\ignoreNew}{Hoc hoc Larmore Ajoy Datta Priyanka Vemula MANETs
MIS clusterhead clusterheads Amis Spohn Aceves multi Fernandess and Malkhi
subsec subsubsec subsubsection LLL ss subgraph mis funcs tbl cllcl fgr lem
CVP cvp eps polylogarithmic sublinear bcircuit tmis ndes altintrfr altdepth
calS alg nc bcp rcp optdom cond alphacases subtrees calD 
breduced alphatree misdisk maxisdisk dstrbtd
thm clstr subtree subgraphs clstrII clstrIII dom le Folkman indep bigs intra}

\marginparwidth 0pt
\oddsidemargin -0.4in %0pt
\marginparsep 0pt
\topmargin  -0.6in
\textwidth   7.2in%6.5in
\textheight  9.1in

\parskip 1.3ex
\parindent 0ex

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[xdvi,dvips]{graphics}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{array}
\usepackage{float}
\usepackage{dsfont}
\usepackage{xspace}
%\usepackage{figlatex}

\graphicspath{{Figures/}{./}}

\input{preamble}
\input{special}

\newcounter{jump}
%\newcounter{jumpaction}
%\newcounter{jumpfunction}

\newcounter{tbl}
\newcounter{fgr}
\newcounter{prp}
\newcounter{action}
\newcounter{priority}

%\renewcommand{\linecomment}[1]{}
%\renewcommand{\datecomment}[1]{}
%\renewcommand{\bfcomment}[1]{{}}


\renewcommand{\Label}{\label}
\renewcommand{\Ref}{\ref}
\renewcommand{\Refstepcounter}{\refstepcounter}

\renewcommand{\today}{}

\raggedbottom


\title{The SMAWK Algorithm}

\author{Lawrence L. Larmore\and UNLV}

\begin{document}

\maketitle

\section{Introduction}


The SMAWK algorithm finds all row minima of a totally monotone matrix,
such as the one below.
The name ``SMAWK" is an acronym consisting of the first letters of the
last names of the five developers of the algorithm.
\cite{smawk87}

\paragraph{Monotonicity.}
A $2\times 2$ matrix $\brackd{\begin{array}{cc}a&b\\c&d\end{array}}$
is defined to be {\em monotone\/} if the following two conditions hold:
\begin{enumerate}
\item
If $c<d$, then $a < b$.
\item
If $c=d$, then $a\le b$.
\end{enumerate}
A rectangular matrix is defined to be {\em totally monotone\/} if
every $2\times 2$ submatrix is monotone.  Recall that a submatrix
does not have to consist of adjacent rows or columns.  For example,
$\brackd{\begin{array}{cc}28&37\\44&33\end{array}}$ is a submatrix
of the $9\times 18$ matrix shown below, obtained by taking the
$3^\rd$ and $6^\tH$ rows and the $7^\tH$ and $9^\tH$ columns.


\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 &25 &21 &13 &10 &20 &13 &19 &35 &37 &41 &58 &66 &82 &99&124&133&156&178
\\
\hline
2 &42 &35 &26 &20 &29 &21 &25 &37 &36 &39 &56 &64 &76 &91&116&125&146&164
\\
\hline
3 &57 &48 &35 &28 &33 &24 &28 &40 &37 &37 &54 &61 &72 &83&107&113&131&146
\\
\hline
4 &78 &65 &51 &42 &44 &35 &38 &48 &42 &42 &55 &61 &70 &80&100&106&120&135
\\
\hline
5 &90 &76 &58 &48 &49 &39 &42 &48 &39 &35 &47 &51 &56 &63 &80 &86 &97&110
\\
\hline
6&103 &85 &67 &56 &55 &44 &44 &49 &39 &33 &41 &44 &49 &56 &71 &75 &84 &96
\\
\hline
7&123&105 &86 &75 &73 &59 &57 &62 &51 &44 &50 &52 &55 &59 &72 &74 &80 &92
\\
\hline
8&142&123&100 &86 &82 &65 &61 &62 &50 &43 &47 &45 &46 &46 &58 &59 &65 &73
\\
\hline
9&151&130&104 &88 &80 &59 &52 &49 &37 &29 &29 &24 &23 &20 &28 &25 &31 &39
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in


The algorithm uses two reductions, which are applied alternately and
recursively.
The first reduction, which we call INTERPOLATE,
reduces the problem of finding the
row minima of an $n\times m$ totally monotone matrix to the problem of
finding the row minima of a $\floor{\frac{n}{2}}\times m$ totally monotone
matrix.  We use this reduction when $m \le n$.

The second reduction, which we call REDUCE, reduces the problem of finding
the row minima of an $n\times m$ totally monotone matrix to the problem
of finding the row minima of an $n\times m'$ totally monotone matrix for
some $m'\le n$.  We use this reduction when $m > n$.


\section{REDUCE}

Since our example matrix has more columns than rows, we will start
with REDUCE.

Consider an $n\times m$ totally monotone matrix $M$.  Write $M\brackd{i,j}$
for the entry of $M$ in the $i\tH$ row and the $j^\tH$ column.
We write $C_j$ for the $j\tH$ column of $M$.

The fundamental idea of REDUCE is to compare two entries in the same row,
and then to use the monotonicity property to eliminate part of one of the
two columns.  More specifically, if $M\brackd{i,j} < M\brackd{i,k}$,
for $j < k$,
we can eliminate all entries of the form $M\brackd{\ell,j}$, for $\ell \ge i$,
from consideration.  On the other had, if $M\brackd{i,j} > M\brackd{i,k}$,
we can eliminate all entries of the form $M\brackd{\ell,k}$, for $\ell \le i$.
If they are equal, we get our choice.

Our goal is to delete at least $m-n$ columns of $M$.  We then continue
SMAWK on the matrix consisting of the surviving columns.

We maintain a stack $S$ of {\em surviving columns}.  Each column on the stack
has a {\em head\/} which is its topmost {\em surviving entry\/}.
All entries of a column on the stack which are above the head are deleted.
Initially, $S$ is empty.

We process the columns one at a time, from left to right.
When we process the column $C_j$, we execute the following steps.

\begin{enumerate}
\item
If $S$ is empty, push the $C_j$ onto the stack, and mark its
first entry \ie the entry in row 1, as its head.
\item
Otherwise, iterate the following loop until either $S$ is empty
or $C_j$ is {\em defeated\/}.
\begin{enumerate}
\item
Let $C_\ell$ be the top entry of $S$.  Let $M\brackd{i,\ell}$
be the head of $C_\ell$.
\item
Compare $M\brackd{i,\ell}$ and $M\brackd{i,j}$.
We will then execute one of the following three steps.
\begin{enumerate}
\item
If $M\brackd{i,j}\le M\brackd{i,\ell}$, then pop $C_\ell$ off $S$.
$C_\ell$ has now been eliminated.  (The loop continues, as $C_j$
attacks the next column on the stack.)
\item
If $M\brackd{i,j} > M\brackd{i,\ell}$ and $i=n$, then $C_j$ is
defeated and eliminated.  Exit the loop.
\item
If $M\brackd{i,j} > M\brackd{i,\ell}$ and $i < n$, then $C_j$ is
defeated, but still survives.  Push $C_j$ onto $S$, and mark
$M\brackd{i+1,j}$ as its head.  Exit the loop.
\end{enumerate}
\end{enumerate}
\end{enumerate}

When all columns have been processed, the heads of all surviving columns
are in different rows.  Thus, there can be at most $n$ surviving columns.
The reduced matrix consists of all surviving columns and all rows.
The row minima of the reduced matrix are the row minima of $M$.

\subsection{An Example Execution of REDUCE}
We will walk through REDUCE for the matrix given in the introduction.

We first push $C_1$ onto $S$.  $S$ consists only of $C_1$, and the head
of that columns is enclosed in a square.


\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 &
\mybox{25}
 &21 &13 &10 &20 &13 &19 &35 &37 &41 &58 &66 &82 &99&124&133&156&178
\\
\hline
2 &42 &35 &26 &20 &29 &21 &25 &37 &36 &39 &56 &64 &76 &91&116&125&146&164
\\
\hline
3 &57 &48 &35 &28 &33 &24 &28 &40 &37 &37 &54 &61 &72 &83&107&113&131&146
\\
\hline
4 &78 &65 &51 &42 &44 &35 &38 &48 &42 &42 &55 &61 &70 &80&100&106&120&135
\\
\hline
5 &90 &76 &58 &48 &49 &39 &42 &48 &39 &35 &47 &51 &56 &63 &80 &86 &97&110
\\
\hline
6&103 &85 &67 &56 &55 &44 &44 &49 &39 &33 &41 &44 &49 &56 &71 &75 &84 &96
\\
\hline
7&123&105 &86 &75 &73 &59 &57 &62 &51 &44 &50 &52 &55 &59 &72 &74 &80 &92
\\
\hline
8&142&123&100 &86 &82 &65 &61 &62 &50 &43 &47 &45 &46 &46 &58 &59 &65 &73
\\
\hline
9&151&130&104 &88 &80 &59 &52 &49 &37 &29 &29 &24 &23 &20 &28 &25 &31 &39
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

In the next step, $C_2$ challenges and eliminates $C_1$.  Since $S$ is now
empty, $C_2$ is pushed onto the stack, with head $M\brackd{1,2}$.

\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 & &
\mybox{21}
 &13 &10 &20 &13 &19 &35 &37 &41 &58 &66 &82 &99&124&133&156&178
\\
\hline
2 &&35 &26 &20 &29 &21 &25 &37 &36 &39 &56 &64 &76 &91&116&125&146&164
\\
\hline
3 &&48 &35 &28 &33 &24 &28 &40 &37 &37 &54 &61 &72 &83&107&113&131&146
\\
\hline
4 &&65 &51 &42 &44 &35 &38 &48 &42 &42 &55 &61 &70 &80&100&106&120&135
\\
\hline
5 &&76 &58 &48 &49 &39 &42 &48 &39 &35 &47 &51 &56 &63 &80 &86 &97&110
\\
\hline
6&&85 &67 &56 &55 &44 &44 &49 &39 &33 &41 &44 &49 &56 &71 &75 &84 &96
\\
\hline
7&&105 &86 &75 &73 &59 &57 &62 &51 &44 &50 &52 &55 &59 &72 &74 &80 &92
\\
\hline
8&&123&100 &86 &82 &65 &61 &62 &50 &43 &47 &45 &46 &46 &58 &59 &65 &73
\\
\hline
9&&130&104 &88 &80 &59 &52 &49 &37 &29 &29 &24 &23 &20 &28 &25 &31 &39
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

In the next two steps, $C_3$ challenges and eliminates $C_2$, and
$C_4$ challenges and eliminates $C_3$.  The resulting matrix:

\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 & &
 &&\mybox{10} &20 &13 &19 &35 &37 &41 &58 &66 &82 &99&124&133&156&178
\\
\hline
2 &&&&20 &29 &21 &25 &37 &36 &39 &56 &64 &76 &91&116&125&146&164
\\
\hline
3 &&&&28 &33 &24 &28 &40 &37 &37 &54 &61 &72 &83&107&113&131&146
\\
\hline
4 &&&&42 &44 &35 &38 &48 &42 &42 &55 &61 &70 &80&100&106&120&135
\\
\hline
5 &&&&48 &49 &39 &42 &48 &39 &35 &47 &51 &56 &63 &80 &86 &97&110
\\
\hline
6&&&&56 &55 &44 &44 &49 &39 &33 &41 &44 &49 &56 &71 &75 &84 &96
\\
\hline
7&&&&75 &73 &59 &57 &62 &51 &44 &50 &52 &55 &59 &72 &74 &80 &92
\\
\hline
8&&&&86 &82 &65 &61 &62 &50 &43 &47 &45 &46 &46 &58 &59 &65 &73
\\
\hline
9&&&&88 &80 &59 &52 &49 &37 &29 &29 &24 &23 &20 &28 &25 &31 &39
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

In the next step, $C_5$ challenges $C_4$ and is defeated.  It is then
pushed onto $S$, with head $M\brackd{2,5}$.

\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 & &
 &&\mybox{10} &&13 &19 &35 &37 &41 &58 &66 &82 &99&124&133&156&178
\\
\hline
2 &&&&20 &\mybox{29} &21 &25 &37 &36 &39 &56 &64 &76 &91&116&125&146&164
\\
\hline
3 &&&&28 &33 &24 &28 &40 &37 &37 &54 &61 &72 &83&107&113&131&146
\\
\hline
4 &&&&42 &44 &35 &38 &48 &42 &42 &55 &61 &70 &80&100&106&120&135
\\
\hline
5 &&&&48 &49 &39 &42 &48 &39 &35 &47 &51 &56 &63 &80 &86 &97&110
\\
\hline
6&&&&56 &55 &44 &44 &49 &39 &33 &41 &44 &49 &56 &71 &75 &84 &96
\\
\hline
7&&&&75 &73 &59 &57 &62 &51 &44 &50 &52 &55 &59 &72 &74 &80 &92
\\
\hline
8&&&&86 &82 &65 &61 &62 &50 &43 &47 &45 &46 &46 &58 &59 &65 &73
\\
\hline
9&&&&88 &80 &59 &52 &49 &37 &29 &29 &24 &23 &20 &28 &25 &31 &39
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

In the next step, $C_6$ challenges and eliminates $C_5$, since $21 \le 29$.
It then challenges $C_4$ and is defeated, since $13 > 10$.

\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 & &
 &&\mybox{10} && &19 &35 &37 &41 &58 &66 &82 &99&124&133&156&178
\\
\hline
2 &&&&20 &&\mybox{21} &25 &37 &36 &39 &56 &64 &76 &91&116&125&146&164
\\
\hline
3 &&&&28 &&24 &28 &40 &37 &37 &54 &61 &72 &83&107&113&131&146
\\
\hline
4 &&&&42 &&35 &38 &48 &42 &42 &55 &61 &70 &80&100&106&120&135
\\
\hline
5 &&&&48 &&39 &42 &48 &39 &35 &47 &51 &56 &63 &80 &86 &97&110
\\
\hline
6&&&&56 &&44 &44 &49 &39 &33 &41 &44 &49 &56 &71 &75 &84 &96
\\
\hline
7&&&&75 &&59 &57 &62 &51 &44 &50 &52 &55 &59 &72 &74 &80 &92
\\
\hline
8&&&&86 &&65 &61 &62 &50 &43 &47 &45 &46 &46 &58 &59 &65 &73
\\
\hline
9&&&&88 &&59 &52 &49 &37 &29 &29 &24 &23 &20 &28 &25 &31 &39
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

In the next step, $C_7$ challenges $C_6$ and is defeated, since
$21 < 25$.  In the following step, $C_8$ challenges $C_7$ and is
defeated, since $28 < 40$.

\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 & &
 &&\mybox{10} && &&&37 &41 &58 &66 &82 &99&124&133&156&178
\\
\hline
2 &&&&20 &&\mybox{21} &&&36 &39 &56 &64 &76 &91&116&125&146&164
\\
\hline
3 &&&&28 &&24 &\mybox{28} &&37 &37 &54 &61 &72 &83&107&113&131&146
\\
\hline
4 &&&&42 &&35 &38 &\mybox{48} &42 &42 &55 &61 &70 &80&100&106&120&135
\\
\hline
5 &&&&48 &&39 &42 &48 &39 &35 &47 &51 &56 &63 &80 &86 &97&110
\\
\hline
6&&&&56 &&44 &44 &49 &39 &33 &41 &44 &49 &56 &71 &75 &84 &96
\\
\hline
7&&&&75 &&59 &57 &62 &51 &44 &50 &52 &55 &59 &72 &74 &80 &92
\\
\hline
8&&&&86 &&65 &61 &62 &50 &43 &47 &45 &46 &46 &58 &59 &65 &73
\\
\hline
9&&&&88 &&59 &52 &49 &37 &29 &29 &24 &23 &20 &28 &25 &31 &39
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

In the next step, $C_9$ challenges and eliminates $C_8$,
and then challenges $C_7$ and is defeated.  In the following
step, $C_{10}$ challenges and eliminates $C_9$, since $42 \le 42$.
Then, $C_{10}$ challenges $C_7$ and is defeated.

\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 & &
 &&\mybox{10} && &&&&&58 &66 &82 &99&124&133&156&178
\\
\hline
2 &&&&20 &&\mybox{21} &&&&&56 &64 &76 &91&116&125&146&164
\\
\hline
3 &&&&28 &&24 &\mybox{28} &&&&54 &61 &72 &83&107&113&131&146
\\
\hline
4 &&&&42 &&35 &38 &&&\mybox{42} &55 &61 &70 &80&100&106&120&135
\\
\hline
5 &&&&48 &&39 &42 & &&35 &47 &51 &56 &63 &80 &86 &97&110
\\
\hline
6&&&&56 &&44 &44 &&&33 &41 &44 &49 &56 &71 &75 &84 &96
\\
\hline
7&&&&75 &&59 &57 &&&44 &50 &52 &55 &59 &72 &74 &80 &92
\\
\hline
8&&&&86 &&65 &61 &&&43 &47 &45 &46 &46 &58 &59 &65 &73
\\
\hline
9&&&&88 &&59 &52 &&&29 &29 &24 &23 &20 &28 &25 &31 &39
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

In the next five steps, each new column is defeated in its first
challenge, and gets pushed onto $S$, because
$55 > 42$, $51 > 47$, $49 > 44$, $59 > 55$, and $58 > 46$.


\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 & &
 &&\mybox{10} && &&&&&&&&&&133&156&178
\\
\hline
2 &&&&20 &&\mybox{21} &&&&&&&&&&125&146&164
\\
\hline
3 &&&&28 &&24 &\mybox{28} &&&&&&&&&113&131&146
\\
\hline
4 &&&&42 &&35 &38 &&&\mybox{42} &&&&&&106&120&135
\\
\hline
5 &&&&48 &&39 &42 & &&35 &\mybox{47} &&&&&86 &97&110
\\
\hline
6&&&&56 &&44 &44 &&&33 &41 &\mybox{44} &&&&75 &84 &96
\\
\hline
7&&&&75 &&59 &57 &&&44 &50 &52 &\mybox{55} &&&74 &80 &92
\\
\hline
8&&&&86 &&65 &61 &&&43 &47 &45 &46 &\mybox{46} &&59 &65 &73
\\
\hline
9&&&&88 &&59 &52 &&&29 &29 &24 &23 &20 &\mybox{28} &25 &31 &39
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

In the next step, $C_{16}$ challenges and eliminates $C_{15}$,
and then challenges $C_{14}$ and is defeated.

\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 & &
 &&\mybox{10} && &&&&&&&&&&&156&178
\\
\hline
2 &&&&20 &&\mybox{21} &&&&&&&&&&&146&164
\\
\hline
3 &&&&28 &&24 &\mybox{28} &&&&&&&&&&131&146
\\
\hline
4 &&&&42 &&35 &38 &&&\mybox{42} &&&&&&&120&135
\\
\hline
5 &&&&48 &&39 &42 & &&35 &\mybox{47} &&&&&&97&110
\\
\hline
6&&&&56 &&44 &44 &&&33 &41 &\mybox{44} &&&&&84 &96
\\
\hline
7&&&&75 &&59 &57 &&&44 &50 &52 &\mybox{55} &&&&80 &92
\\
\hline
8&&&&86 &&65 &61 &&&43 &47 &45 &46 &\mybox{46} &&&65 &73
\\
\hline
9&&&&88 &&59 &52 &&&29 &29 &24 &23 &20 &&\mybox{25}&31 &39
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

In the last two steps, $C_{17}$ and $C_{18}$ each challenge
$C_{16}$ and are defeated.  However, since the head of $C_{16}$
is in the $n^\tH$ row, these columns are eliminated and not
pushed onto $S$.

\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 & &
 &&\mybox{10} && &&&&&&&&&&&&
\\
\hline
2 &&&&20 &&\mybox{21} &&&&&&&&&&&&
\\
\hline
3 &&&&28 &&24 &\mybox{28} &&&&&&&&&&&
\\
\hline
4 &&&&42 &&35 &38 &&&\mybox{42} &&&&&&&&
\\
\hline
5 &&&&48 &&39 &42 & &&35 &\mybox{47} &&&&&&&
\\
\hline
6&&&&56 &&44 &44 &&&33 &41 &\mybox{44} &&&&&&
\\
\hline
7&&&&75 &&59 &57 &&&44 &50 &52 &\mybox{55} &&&&&
\\
\hline
8&&&&86 &&65 &61 &&&43 &47 &45 &46 &\mybox{46} &&&&
\\
\hline
9&&&&88 &&59 &52 &&&29 &29 &24 &23 &20 &&\mybox{25}&&
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

The row minima of $M$ must be located in the entries that
have not been eliminated.  They need not be the heads of the
columns.

We continue the recursion by executing SMAWK on the
square matrix consisting of the surviving columns:

\vskip 0.1in

\begin{center}
$\begin{array}{ c||c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|}
&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
\\
\hline\hline
1 &&&&10 &&13 &19 &&&41 &58 &66 &82 &99&&133&&
\\
\hline
2 &&&&20 &&21 &25 &&&39 &56 &64 &76 &91&&125&&
\\
\hline
3 &&&&28 &&24 &28 &&&37&54 &61 &72 &83&&113&&
\\
\hline
4 &&&&42 &&35 &38 &&&42 &55 &61 &70 &80&&106&&
\\
\hline
5 &&&&48 &&39 &42&&&35 &47 &51 &56 &63 &&86 &&
\\
\hline
6&&&&56 &&44 &44 &&&33 &41 &44 &49 &56 &&75 &&
\\
\hline
7&&&&75 &&59 &57 &&&44 &50 &52 &55 &59 &&74 &&
\\
\hline
8&&&&86 &&65 &61 &&&43 &47 &45 &46 &46 &&59 &&
\\
\hline
9&&&&88 &&59 &52 &&&29 &29 &24 &23 &20 &&25 &&
\\
\hline
\end{array}$
\end{center}

\vskip 0.1in

Since the reduced matrix has at least as many rows as columns, the
recursive application of SMAWK will begin with INTERPOLATE.
Despite the fact that we know that almost half the reduced matrix could not
contain any row minima, we do not use this information in the next step.

\section{INTERPOLATE}

\begin{small}
\bibliographystyle{plain}
%\bibliography{../../Research/dstrbtd}
\bibliography{smawk}
\end{small}

\end{document}
