   % http://www.chiark.greenend.org.uk/~sgtatham/putty/download.html


\documentclass[11pt,fleqn]{article}
\usepackage{fig/psfig}
\usepackage{fig/fullpage}
\usepackage{bbm}
\usepackage{amsmath,amssymb,amsthm}

\newcommand{\wi}{\widehat{i}}

\newcommand{\D}{\mathcal D} 


\begin{document}

\input{lib_commands.tex}

\title{ {\Large\bf
A Faster Approximate Minimum Steiner Tree Algorithm \\
\& Primal-Dual and Local-Ratio Greedy Algorithms}}

\author{
{\large\bf\sl H. Kwon}
\thanks{York University, Canada. james@cs.yorku.ca.}
\and
{\large\bf\sl Jeff Edmonds}
\thanks{York University, Canada. jeff@cs.yorku.ca. Supported in
part by NSERC Canada.}
\and
{\large\bf\sl A.\ Borodin}
\thanks{
University of Toronto.
bor@cs.toronto.edu.}
}
\date{}
\maketitle


\begin{abstract}
We prove matching upper and lower bounds for the Minimum Steiner Tree
(MStT) problem within the adaptive priority stack model introduced by
Borodin, Cashman, and Magen \cite{BCM05} and lower bounds 
 within the adaptive priority queue model introduced here.
These models, which are
extensions of the adaptive priority model of Borodin, Nielson, and
Rackoff \cite{BNR02}, are said to capture reasonable primal-dual and
local-ratio extensions of greedy algorithms.  Borodin
etal.\ \cite{BCM05} had proved lower bound $1 \frac{1}{3}$ on the
approximation ratio obtainable for the problem in the stack model. We
improve this to $2\!-\!{\tiny \bigO(\frac{1}{|V|})}$.  This and
similar results prove that the above upper bound is tight, that the
adaptive priority stack model is incomparable with the fully adaptive
priority branching tree (pBT) model, and that the online stack model
is incomparable with the adaptive priority model.  We also prove a
lower bound in the priority model for complete graphs improving the
result of Davis and Impagliazzo \cite{DI04} from $1 \frac{1}{4}$ to $1
\frac{1}{3}$. The priority queue model is better because ?????
Within it we prove a $7 \over 6$ approximation lower bound.
\end{abstract}

\newcommand{\I}{\Phi}

\newcommand{\bcodep}[3]{
{\noindent {\bf algorithm}} {#1}
{\\ $\left< input \right>$:} {#2}
{\\ $\left< output \right>$:} {#3} 
\\ begin \vspace{-1.9ex}\bcodefrag
}

\section{Introduction}

We are interested in how well {\em greedy algorithms} and their {\em
primal-dual} and {\em local ratio} extensions are able to approximate
various variations of the Minimum Steiner Tree Problem.
Borodin, Nielsen and Rackoff, \cite{BNR02}, introduced the {\em
  priority model} which captures reasonable greedy or greedy-like
algorithms.  The paper of Borodin, Cashman, and Magen \cite{BCM05}
formalized a computational model referred to as the {\em priority
  stack model} that captures both the primal-dual and the local ratio
algorithm design paradigms.
The priority queue model is better because ?????

The Minimum Steiner Tree (MST) problem of finding a minimum subtree 
that spans the terminal nodes has practical applications such
as routing VLSI layout, the design of communication networks, and
accounting and billing for the use of telephone networks
\cite{GHNP00}. It is NP-complete.

The best known approximation algorithm \cite{DI04} for the general
MStT problem without any triangle inequality restrictions achieves
1.55 performance guarantee, but it likely fits neither into the
priority model nor the stack model. There is a much easier algorithm
that achieves a 2-approximation \cite{2MStT}.  Simply do a Minimum
Spanning Tree on $G^c_R$, where $G^c_R$ is the graph on the terminal
nodes $R$ with weight on edge $\{u,v\}$ being the weight of the
minimum path from $u$ to $v$ in $G$.  We show how to express this
algorithm within the {\em adaptive priority stack} model. Given that
Davis and Impagliazzo \cite{DI?}  show how to implement Dijkstra
single source all destination shortest paths algorithm in the adaptive
priority model, it is not hard to see how to do $st$-connectivity in
the adaptive priority stack model. Minimum spanning tree is the
classic algorithm in the fixed priority model.  Hence, each step of
this MStT algorithm can be implemented by an adaptive priority stack
algorithm. However, because this model only allows the algorithm to
pass once through the data items, the trick when implementing this
algorithm was to prove that it works correctly when all of these tasks
are performed simultaneously.  Inadvertently, doing so improved the
running time of this algorithm from the number $|R|$ of terminal
nodes times the running time $\bigO(|V| \log |V|+|E|)$ of Dijkstra's
algorithm to being only the time $\bigO(|V| \log |V|+|E|)$ of
Dijkstra's algorithm once on $G$.

We also get a 2-approximation algorithm in weaker models when the MStT
problem is restricted, namely within the {\em fixed priority stack}
model when there are no edges between the Steiner nodes, within the
{\em online stack} model when there are no edges between the Steiner
nodes and the weight of every edge included is one, and within the
{\em fixed priority} model when the triangle inequality holds.

Now let consider lower bounds.   When there are only two Steiner nodes
$s$  and  $t$, MStT  amounts  to  $st$-connectivity,  which Davis  and
Impagliazzo  \cite{DI10}  prove  cannot  be  solved by  a  {\em  fully
adaptive  priority  branching  tree}  (pBT) algorithm  unless  it  has
exponential width.  This proves for  the first time that this model is
incomparable with the adaptive priority model. Previously the adaptive
priority  stack model  had been  separated from  the much  weaker {\em
priority} model for a  packing problem (weighted interval scheduling),
but this  is the first  such separation for  a problem that is  both a
graph problem and a covering problem.

When MStT is restricted so that there are no edges between the Steiner
nodes, there is no longer a $st$-connectivity aspect to the MStT
problem.  Borodin, Cashman, Magen \cite{BCM05} proved a lower bound
that no adaptive priority stack algorithm can achieve an approximation
ratio better than $1{1 \over 3}$ in this case even it when restricted
to any of the variations listed above. We improve this lower bound to
$2 - \bigO({1 \over |V|})$, making it tight. Our lower bound is also
in a slightly stronger model in which the algorithm is able to accept
{\em implicit} edges.

We also obtain an arbitrarily large lower bound on the approximation
ratio obtained by an adaptive priority algorithm for the MStT problem
when it does not need to satisfy the triangle inequality, even when
there are no edges between the Steiner nodes are allowed and the
weight of every edge included is one.  This proves that the online
stack model is incomparable with the adaptive priority model.  The
arbitrarily high lower bound also holds when, though the triangle
inequality ''holds,'' and all terminal-terminal edges are implicit and
cannot be accepted. This gives the first separation between the
initially defined priority model in which implicit edges cannot be
accepted and our new strengthening of the model in which they can.

Davis and Impagliazzo Davis \cite{DI04}, before the \cite{BCM05}
results, give a lower bound of $1{1 \over 4}$ within the adaptive
priority model when the instance graph to MStT must be complete. We
improve this result by increasing the bound to $1{1 \over 3}$.  A
weakness of these complete graph lower bounds is that they apply only
to graphs of fixed size and hence do not prove that the error is
multiplicative instead of additive. We give some intuition as to why
proving this same result for arbitrarily large complete graphs would
be hard. Proving the same result for in the stack model also seems
hard.

Within the priority queue model, we prove a $7 \over 6$ approximation
lower bound.

\newcommand{\xx}[1]{\parbox{3.3in}{#1}}

\begin{table}[hbtp]
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|} \hline
& \multicolumn{2}{|c|}{adaptive priority} 
& \multicolumn{3}{|c|}{priority stack} \\ \hline
&  &
br.\ tree &
online &
fixed &
adaptive 
\\ \hline \hline
% 
\xx{general MStT} 
& $\infty$ & $\infty$ & $\infty'$ & $\infty'$ & 2 \\ \hline
%
\xx{no edges between the Steiner nodes} 
& $\infty$ & 1 & $\infty'$ & 2 & 2 \\ \hline
%
\xx{\& the weight of every edge included is one} 
& $\infty$ & 1 & 2 & 2 & 2 \\ \hline
%
\xx{the triangle inequality holds} 
& 2 & 2 & $\infty'$ & $\infty'$ & 2 \\ \hline
%
\xx{complete \& the triangle inequality holds} 
& $\ge 1{1 \over 3}$ & $\infty$ & \multicolumn{3}{|c|}{?} \\ \hline
\end{tabular}
\caption{\label{tab:mstp-summary} Summary of the known results and
  results presented in this paper for the MST problem.
Here $\infty'$ means that we assume that no constant approximation
  algorithm possible in the model, but we have not looked for a proof.
}
\end{center} \end{table}

\rsec{sec:preliminaries}
provides the preliminary definitions,
\rsec{sec upper} provides the upper bounds,
and \rsec{sec lower} provides the lower bounds.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Preliminaries}
\label{sec:preliminaries}

In this section, we define the {\em Minimum Steiner Tree} problem
(MStT), the {\em priority model}, and the {\em priority Stack model}.

\begin{description}
\i[A General Computational Problem:] An {\em optimization problem} with
priority model $(\D, \Sigma)$ and a family of objection
functions $f^n:\D^n\times \Sigma^n \rightarrow \mathbb{R}$ is
defined as follows. An instance $I = \left\{ D_1, D_2, \ldots, D_n
\right\} \in \D^n$ is specified by a set of $n$ {\em data items} $D_i$
chosen from the given domain $\D$. A solution for the instance is
consists of a decision $a_i \in \Sigma$ made about each data item
$d_i$ in the instance $I$, namely a set of tuples, $S=\{(D_i, a_i) |
D_i \in I\}$.  An exact algorithm must find a solution that minimizes
(maximizes) $f(I,S)$.  An $\mathcal{R}$-approximation algorithms finds
one within a factor of $\mathcal{R}$ of this optimal value.

\i[The Minimum Steiner Tree (MStT) problem:] A data item for the MStT
problem in the edge model is a weighted edge $D_i =
\left<\{u,v\},w\right>$ with the knowledge that the nodes in
$N \subseteq V$ are {\em terminal} nodes and those in $V \setminus N$
are \textit{Steiner} nodes. The decision $a_i \in \Sigma = \{accepted,
rejected\}$ to be made is whether to include the edge in the
solution. If the resulting solution is a {\em Steiner tree}, i.e.\ it
spans all the terminal nodes of the instance graph $G$, then its cost
is $f(I,S) = \sum_{a_i = accept} w_i$.  If the {\em triangle
inequality} is said to hold then $w(\{u,v\})) \le w(\{u,x\}) +
w(\{x,v\})$.

\i[Adaptive Priority Algorithms:] \cite{BNR02} models {\em greedy}
algorithms with the {\em adaptive priority} model.  A {\em greedy}
algorithm receives the data items $D_i$ one at a time and must make an
irrevocable decision $a_i$ about each as it arrives. For example, an
algorithm for MStT might accept the edge as long as it does not create
a cycle. We will assume that the algorithm has unbounded computational
power based on what it knows from the data items it has seen
already. The algorithm's lack of ability to find an optimal solution
arises because it does not know the data items that it has not yet
seen.  The algorithm, however, is given the additional power to be
able specify a priority ordering function (greedy criteria) and is
ensured that it will see the data items in this order. For example, an
algorithm for MStT may request the cheapest edges between terminal
nodes first.  \cite{BNR03} allows the algorithm to specify the
priority order without allowing it to see the future data items by
having it specifying an ordering $\pi \in \mathcal O(\D)$ of all
possible data items.  The algorithm then receives the next data item
$D_i$ in the actual input according this order.  An added benefit of
ordering the data items is that when receiving the data item $D$, the
algorithm inadvertently learns that every data item $D'$ before $D$ in
the priority ordering is not in the input instance.

\bcodep
{Adaptive Priority Algorithm}
{$I = \{D_1, \ldots, D_n\}$}
{$S = \{(D_i,a_i) |\ 1 \le i \le n\}$}
 \> Loop: {$i=1,2, \ldots, n$}\\
\>  \> \loopinv{Assume the data items $\left<D_1, D_2,
\ldots, D_{i-1}\right>$ have been seen and processed.
This is all that the algorithm knows about the instance.} \\
\> \> Choose a possible new ordering $\Pi$ on all
possible data items. \\
\> \> Let $D_i$ be the next data item according
to this new order. \\
\> \> Make an irrevocable decision $a_{\pi_i}$ about the
data item $D_i$.\\
 \> \> Update the solution: $S = S \cup \{(D_i, a_{\pi_i})\}$.\\
 \> end Loop\\
 \> Output $S = \{(D_i,a_i) |\ 1 \le i \le n\}$.\\
\ecode

\i[Online, Fixed, and Adaptive Priorities:] An adaptive priority
algorithm as described above is said to be {\em adaptive} because it
is able to change its priority order $\Pi$ on the data items each time
it sees a new item. In contrast, it is called a {\em fixed priority}
algorithm if it chooses one order that is fixed for the duration of
the algorithm, and it is called an {\em online} algorithm if an
adversary chooses the order in which the data items are seen.

\i[Accepting Implicit Edges:] Normally, an edge not in the instance
graph cannot be included in the solution.  In order to gives the
algorithm more flexibility, we strengthen the model so they can. An
edge is said to be {\em implicit} if is is not explicitly mentioned in
the instance. Its weights is assumed to be that imposed by the
triangle inequality, (i.e.\ the weight of a missing edge $\{u,v\}$ is
the length of the shortest path from $u$ to $v$ amongst the included
edges).  The algorithm can accept or reject an implicit edge any
time. This decision however will have to be made without explicitly
learning the weight of the edge.  Hence, there is no advantage to
doing so until after all the explicit edges have been seen.  The key
thing that such an algorithm cannot do is to initially learn about $u$
and $v$ by saying ``Give me the most expensive implicit edge and I
will reject it.''  Note that this addition to the model only makes
sense when the triangle inequality holds.

\i[Stack:] 
Borodin, Cashman, and Magen \cite{BCM05} define a new model referred to
as the {\em adaptive stack model}. They advocate that their model
captures reasonable primal-dual algorithms and local-ratio
algorithms. The weakness of the adaptive priority model is that the
algorithm must make an irrevocable decision on the chosen data item,
that is, $a_i \in \sum = \{\textit{accept},\textit{reject}\}$. The
stack model gives the algorithm a second phase in which it can reject
previously ``accepted'' data items.

The adaptive stack model allows the algorithm to have two phases. The
first phase is the same as the adaptive priority algorithms except
that the stack algorithm has a stack and a choice set $\Sigma =
\{\textit{reject},\ \textit{stack}\}$. The rejected data items are
permanently discarded by the algorithm, whereas stacked items are
pushed on the top of the stack. 

The data items that are placed in the stack are processed during the
second phase, which is called the \textit{pop} or {\it clean up}
phase. Each data item is popped in the reverse of the processed order
in the first phase. Each time an item is popped, the algorithm {\em is
forced to discard} it if the data items that have been previously been
popped and accepted together with those remaining in the stack create
a feasible solution. Otherwise, the popped item {\em is forced to be
included} in the algorithm's solution.

Note that the stack model is carefully designed to give the algorithm
no control over the second phase. If the algorithm had control over
the second phase, then it could read all of the data items during the
first phase and push them all onto the stack. Then, knowing the entire
input instance, it can use its unlimited power to compute the optimal
solution. During the second phase, it could simply accept and reject
the data items corresponding to this solution.



\i[Queue:] We introduced an new (yet obvious) model referred to as the
  {\em adaptive queue model}. It is the same as the previously defined
  model, except that data items are placed on a queue instead of a
  stack. For MStT, we can assume that the popping of the second phase
  does not wait until the pushing phase is completed. In fact, we can
  assume that the queue aways contains a tree of edges that spans the
  terminal nodes (once it initially does). Suppose an edge is added to
  the end of the queue that creates a cycle with what is in the queue.
  Let $e$ denote the edge that is first in the queue of those in this
  new cycle. We know that when second phase considers edge $e$, it
  will be discarded because what remains in the queue still spans the
  terminal nodes.  Hence, we might as well immediately consider $e$
  discarded.

To get some idea of the extra power of having such a queue, suppose we
simplify the situation so that instead of the algorithm receiving a
sequence individual data items, it receives a sequence of possible
solutions. Then there is an online queue algorithm with approximation
ratio $c = \sqrt{f_{max} \over f_{min}}$, where $f_{max}$ and
$f_{min}$ are the maximum and the minimum of any solution value.  The
value $f_{current}$ of the current solution goes up and down as if the
algorithm was walking along a hilly path.  If $f_{current}$ ever
reaches the value $c \cdot f_{min}$ or smaller, then the algorithm
states that it is happy with the solution it has and hence rejects the
remaining possible solutions. Even if the adversary can arrange the
best possible solution with value $f_{min}$, the algorithm has
achieved its required competitive ratio of $c$. On the other hand if,
all the solutions that appear have value at least $c \cdot f_{min}$,
then the algorithm continues until the adversary gets tired and states
that all the possible solutions have been seen. The algorithms
solution at this time can't be worse than $f_{max}$ and the optimal
solution for the instance can't be better than seen by the algorithm
and hence not better than $c \cdot f_{min}$. This gives an
approximation ratio of ${f_{alg} \over f_{opt}} \le {f_{max} \over c
  \cdot f_{min}} = c$.  In our lower bound $f_{max} = 8$, $f_{min} =
5$, $c = \sqrt{f_{max} \over f_{min}} = 1.265$ and following these
same ideas obtained the bounds ${7 \over 6} = 1.167$.  Of course, the
``pseudo'' upper bound presented above does not work in general, because even
though all the individual data items went by, the optimal solution might
never have been in the queue at one point in time. Likely, a stronger lower bound
could be proved using this fact.

\end{description}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Lower Bounds} \label{sec lower}

\rsec{subsec: lb tech} describes the general lower bound technique
introduced in \cite{BNR02}.  \rsec{subsec:large priority} gives the
arbitrarily large lower bounds in the priority model.
\rsec{subsec:queue} gives a $7 \over 6$ lower bound in the priority
queue model.  \rsec{subsec:mstp2stack} gives a $2 -
\bigO(\frac{1}{|V|})$ lower bound in the priority stack model.
Finally, \rsec{subsec:mstp-fixed} gives the $1\frac{1}{3}$ lower bound
in the priority model given a complete graph.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{The Lower Bound Technique}
\label{subsec: lb tech}


A lower bound in the priority model can be described as a game between
an adversary and an algorithm. At the beginning of the $i^{th}$
iteration of the game, the algorithm has been given the partial
instance $PI_{i-1} = \left<D_1,D_2, \ldots,D_{i-1}\right>$ and has
committed to the partial solution $PS_{i-1} =
\left<a_1,a_2,\ldots,a_{i-1}\right>$ and the adversary has narrowed
down the universe of possible data items to $\D_{i-1}$ from which it
promises future data items will chosen.  The algorithm being adaptive
is allowed to reorder the data items in $\D_{i-1}$. The adversary
promises to put in the instance
whichever data item in $\D_{i-1}$ is
the algorithm's favorite. Hence, the game can be
simplified by allowing the algorithm to choose $D_i$ from
$\D_{i-1}$.  The algorithm then must make an irrevocable decision
$a_i$ about $D_i$. Knowing $D_i$ and $a_i$, the
adversary is then allowed to narrow down $\D_{i-1}$ to $\D_i$ by
removing some data items (including $D_i$) that would make the
algorithm's task ``easy''.  Generally, the adversary is allowed to
dynamically choose how many data items there will be in the actual
instance. Hence, the adversary has the power at any point in the game
to declare $I = PI_i$ is the actual instance.  The adversary wins if
$I$ is a valid instance and $S = PS_i$ is not a sufficiently optimal
solution for it.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Arbitrarily Large Lower Bounds in the Priority Model}
\label{subsec:large priority}

\tm{lower priority} We obtain an arbitrarily large lower bound on the
approximation ratio obtained by an adaptive priority algorithm for the
MStT problem when it does not need to satisfy the triangle inequality,
even when there are no edges between the Steiner nodes and the weight
of every Steiner-terminal edge included is one.  The arbitrarily high
lower bound also holds when, though the triangle inequality ''holds,''
all terminal-terminal edges are implicit and cannot be accepted.  \etm

\noindent
This lower bound together with the upper bound in
\rtm{upper online} proves that the online stack model is incomparable
with the adaptive priority model.  Suppose that in the second
scenario, the algorithm was allowed to accept implicit edges.  Because
all the Steiner-terminal edges have weight one and the triangle
inequality holds, the algorithm implicitly knows that the weight on
all terminal-terminal edges have weight 2.  Hence, it can obtain
minimum spanning tree of $G^c_R$ by accepting any spanning tree.
\rtm{tm MST} then gives that this is a 2-approximate solution.  This
gives a separation between the initially defined priority model in
which implicit edges cannot be accepted and our new strengthening of
the model in which they can be.

   % No priority algorithm can achieve a approximation ratio for the MStT
   % problem better than $\min(c (1\!-!{1 \over n_t}),1\!+\!{n_s\!-\!1
   % \over n_t})$, where $n_t$ denotes the number of {\em terminal nodes},
   % $n_s$ denotes the number of {\em Steiner nodes}, $c$ denotes the
   % weight between each pair of terminal nodes, 1 is the weight on the
   % terminal-steiner edges that exist, and their are no steiner-steiner
   % edges.
   % \noindent
   % Note this can be made arbitrarily large by making $c$ large (or
   % removing the terminal edges) and by making the number of Steiner nodes
   % much larger than the number of terminal nodes.

\medskip
\pftm{lower priority} The instance will have $n_t$ terminal nodes and
$n_s$ Steiner nodes. Initially, the universe $\D_0$ of possible data
items consists of all the terminal-terminal edges each of weight $c$,
all terminal-Steiner edges each of weight 1, and no Steiner-Steiner
edges.  Every time the algorithm accepts a Steiner edge, the adversary
deletes all other unseen Steiner edges adjacent to this same steiner
node. That is, if the algorithm has rejected $d$ edges adjacent to the
steiner node $s_j$ and then accepted one adjacent to it, then this
node $s_j$ will have degree $d\!+\!1$ in the actual instance and the
one accepted edge is useless. This continues until either the algorithm has
accepted $n_t\!-\!1$ terminal edges or is about to accept a steiner
edge adjacent to the last Steiner node considered.  At this point, the
adversary declares the actual instance consists of all the edges seen,
all the terminal edges, and the {\em star} of steiner edges from this
last Steiner node $s_{last}$ considered to each terminal node. The
optimal steiner tree, consisting of this star, has weight $n_t$. The
algorithm's total weight is $c(n_t\!-\!1)$ if it accepts $n_t\!-\!1$
terminal edges. Otherwise, the process continued until at least one
Steiner edge is accepted to each steiner node.  Let $a$ denote the
number of terminal edges that the algorithms accepts. Because the
other Steiner edges go no where, it must accept $n_t\!-\!a$ of those
to the last steiner node.  This gives a total cost of $ca + 1 \cdot
(n_s\!-\!1) + 1 \cdot (n_t\!-\!a)$, which when $c \ge 1$ is minimized
by setting $a=0$, giving $n_s\!+\!n_t\!-\!1$.  Hence, $\mathcal{R}=Alg
/ Opt = {\min(c(n_t\!-\!1),n_s\!+\!n_t\!-\!1) \over n_t} = \min(c
(1\!-\!{1 \over n_t}),1\!+\!{n_s\!-\!1 \over n_t})$.  This can be made
arbitrarily large by making $c$ large (or removing the terminal edges)
and by making the number of Steiner nodes much larger than the number
of terminal nodes. \epf


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{A $7 \over 6$-Queue Lower Bound}
\label{subsec:queue}

\tm{thm:queue} No adaptive queue algorithm achieves better than $7
\over 6$ approximation for the MStT problem.  The result still holds even
when there are five terminal nodes, all terminal-terminal edges appear
and have weight two, the Steiner-terminal edges that appear have
weight one, and there are no edges between the Steiner nodes \etm

\noindent
Note that if you prefer the size of the solution to be
arbitrarily large so that we know that the error is multiplicative
instead of additive, than we can repeat this five terminal node
lower bound an arbitrary number of times in parallel.

\medskip

\pftm{thm:queue} As is often the case, the lower bound proof follows
the same ideas as the ``pseudo'' upper bound.  As defined for the
queue model, at each point in time $i$, the queue contains a solution,
i.e.\ a tree of edges that spans the five terminal nodes. See
\rfig{fig:queue}.  The algorithm is able to change this solution by
asking for an edge and adding it to the queue. His goal is to obtain a
solution of low weight. But as if he were following a hilly path, he might
have to go up out of a local minimum before he is able to go down
farther.  The lower bound adversary allows the algorithm to build at
solution of value $f_{current} = c f_{min} = 6.32 \approx 6$. Then the
algorithm has a choice. If he says that he is happy with this
solution, rejecting all unseen edges, then the adversary can reveal a
new Steiner node of degree 5, giving a weight $f_{min} = 5$ solution
for a ratio of ${6 \over 5}$. On the other hand, if the algorithm
wants to continue in hopes to find such a weight 5 solution, the
adversary can ensure that he must first pass through a weight 7
solution. The adversary then states that there are no more edges in
the instance. The algorithm has weight 7, but the optimum is the
previous solution of weight 6 for a ratio of ${7 \over 6}$.
%
 \figc{2in}{fig/queue}{Examples of spanning trees that
  might be in the queue. A node is circled if it is closed. }
{fig:queue}


To decrease the number of cases to be considered, consider each
terminal edge $\{t_k,t_{k'}\}$ as being the pair of Steiner edges
$\{s_j,t_k\}$ and $\{s_j,t_{k'}\}$.  Then, a useful way of viewing the
weight of a tree is the number $r$ of useful Steiner nodes,
i.e.\ those that connect to at least two terminal nodes. Note that if
the algorithm were to stop with such a tree, then the unuseful Steiner
edges, i.e.\ those connected with only one terminal node, are
automatically removed.  A quick check would show that the weight of
the resulting solution is $4+r$. Hence, the goal of the algorithm is
to cover the five terminal nodes with a smaller number $r$ of useful
Steiner nodes. For example, the weight 6 solutions have $r=2$ and
\rfig{fig:queue}.A and C are the only possibilities.

As defined in the lower bound technique, the adversary also maintains
a set $\D_{i-1}$ of the edges that still might get seen. The adversary
will assure that each Steiner node $s_j$ is either considered {\em
  open} in which case all five of its Steiner edges still might be in
the input or is considered {\em closed} in which case all of its not
previously seen Steiner edges have been removed from $\D_{i-1}$ and as
such are known to not be in the input.  Clearly, the adversary will
close a Steiner node before the algorithm can see all five of its
edges.

The adversary is able to drastically reduce the actions that the
algorithm can safely take.  If, for example, the algorithm ever
considers and rejects an edge $\{s_j,t_k\}$, then $s_j$ must have been
open, in which case the adversary can state that all five edges from
$s_j$ are in the instance giving an optimal solution of weight
5. The algorithm, no longer having access to this one rejected
edge, must have weight at least 6, giving a ratio of at least ${6
  \over 5} > {7 \over 6}$.

Just like rejected edges, edges popped from the queue are no longer
available for the algorithm's solution. Hence, the algorithm best not
do this to an open Steiner node's edge. An effect of this is that it
is really best for the algorithm to stick with asking for the edges of
the same Steiner node until the adversary closes it.  In
\rfig{fig:queue}.A, for example, suppose the algorithm chooses not to
continue asking about Steiner node $s_2$'s edges even though it is
still open and instead adds $s_3$'s edges $\{s_3,t_4\}$ and
$\{s_3,t_5\}$.  Because this creates a cycle, the oldest edge in this
cycle, in this case one of $s_2$'s edges, is popped producing
\rfig{fig:queue}.B. The adversary can then win by saying that that
popped edge was needed in the solution of value 5 stemming from $s_2$.
Similarly, suppose that \rfig{fig:queue}.A had been produced by first
adding those edges adjacent to Steiner node $s_2$, but not closing it
moved on to adding those adjacent to $s_1$. Further suppose that the
algorithm then goes back to $s_2$'s edges adding $\{s_2,t_3\}$ to the
queue. The effect of this is that edge $\{s_2,t_4\}$ is popped.
Again, the adversary can then win by saying that that popped edge was
needed.

Now suppose the adversary has allowed the algorithm to build up a
solution of weight 6. As said, there are only two such solutions, that
in \rfig{fig:queue}.A and that in B. We will now complete the proof by
showing that the algorithm cannot continue without increasing the
weight to 7.  From \rfig{fig:queue}.A, if the algorithm continues with
$s_2$ by pushing edge $\{s_2,t_3\}$, then this creates a cycle popping
either $\{s_1,t_3\}$ or $\{s_1,t_4\}$. This produces
\rfig{fig:queue}.C.  From \rfig{fig:queue}.C, (and similarly from
\rfig{fig:queue}.A) if the algorithm asks about other edges then
nothing really changes until it has included a Steiner node $s_3$ with
degree of two.  In each case, this creates a cycle, popping an edge
and increasing the weight to 7.  For example, adding edges
$\{s_3,t_2\}$ and $\{s_3,t_3\}$ produces \rfig{fig:queue}.D.  \epf


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{A $2 - \bigO(\frac{1}{|V|})$ Stack Lower Bound}
\label{subsec:mstp2stack}

Borodin, Cashman, and Magen \cite{BCM05} define a new model referred
to as the {\em adaptive stack model} and within it prove a
$1\frac{1}{3}$ lower bound. We improve this ratio to $2 -
\bigO(\frac{1}{|V|})$.  The result is also strengthened by allowing the
algorithm to accepted or rejected implicit edges at any time.

\tm{thm:mstp2stack} No adaptive stack algorithm achieves better than
$2 - \bigO(\frac{1}{|V|})$ approximation for the MStT problem.  The
result still holds even in the following very restricted setting.  The
triangle inequality holds on the complete graph, though some of the
Steiner-terminal edges only exits implicitly and as such can be
accepted but not requested.  All terminal-terminal edges have weight
2, explicit Steiner-terminal edges have weight 1, implicit
Steiner-terminal edges have weight 3, and Steiner-Steiner (which are
useless) have weight 2.  \etm

\noindent
This lower bound is tight (except for the $-\bigO(\frac{1}{|V|})$)
with the adaptive priority stack algorithm for MStT given in
\rtm{upper no triangle}.  For what it is worth, if you continue to
consider the priority model, but restrict it to being either
fixed-stack, online-stack, or fixed-no-stack, then Theorems \ref{upper
  no triangle fixed}, \ref{upper online}, and \ref{upper triangle} will
show that there is still a 2-approximate algorithm as long as the
graphs are restricted in the appropriate ways.  Because our lower
bounds hold in each of these ways, our result is tight for each of
these restricted models.  Specifically, the triangle inequality holds;
we could assume that the Steiner-Steiner edges do not exist, because
in our lower bound they are effectively useless; the subgraph on the
terminal nodes is complete; unless you want all explicit edges to have
weight one in which case you can delete these terminal-terminal edges.

\medskip
\pftm{thm:mstp2stack}
Our goal is to force the algorithm to stack an expensive solution
followed by a cheap solution. When the cheap solution is popped, it is
forcefully discarded because there is still a feasible solution,
namely the expensive solution, on the stack. Later, on the other hand,
the expensive solution will be kept it is required for the solution
consisting of what is left on the stack and what has already been
accepted. A valid solution for the MStT problem consists of a set of
edges that connect the terminal nodes together. Wanting such a
solution to be pushed on the stack, the adversary will monitor how
well the edges stacked by the algorithm so far connect the terminal
nodes. To do this, the adversary partitions the terminal nodes into
components that are connected via the stacked edges. Note that
$n_t\!-\!c$ ``edges'' are needed to connect the $n_t$ terminal nodes into
$c$ components.

Wanting this solution on the stack to be expensive, the adversary
wants it to cost the algorithm at least 2 for each ``edge'' connecting
two terminal nodes. There are four types of such connecting
``edges''. The first type of ``edge'' is simply a terminal edge
$\left<t_k,t_{k'}\right>$, which as required costs 2. The second type
of ``edge'' consists of two Steiner edges $\left<t_k,s_j\right>$ and
$\left<s_j,t_{k'}\right>$, which also costs $1+1=2$. The third type of
``edge'' needs to be avoided because it is too inexpensive. This
consists of an $\ell$-star from one Steiner node $s_j$, fanning out
with explicit Steiner edges to some $\ell$ of the terminal nodes. This
acts as $\ell\!-\!1$ connecting ``edges'' but only costs $\ell$, as
explicit Steiner edges only cost 1 each. The adversary will avoid
allowing the algorithm to push such stars onto the stack by making any
unseen edges incident to $s_j$ implicit as soon as the algorithm
pushes two explicit edges incident to $s_j$. The final type of
``edge'' involves the algorithm accepting an implicit Steiner
edge. However, these edges cost 3. We will let $r, b,$ and $b'$ denote
the number of accepted ``edges'' of the first, second, and fourth
type. The loop invariant maintains that $r\!+\!b\!+\!b' \geq
n_t\!-\!c$ which reconfirms that the number of these ``edges'' is at
least the $n_t\!-\!c$ needed to connect the terminal nodes into $c$
connected components. Having enough intuition, we are now ready to
prove the theorem.

Before the $i^{th}$ iteration, the set of edges that are still
possibly in the instance is denoted $\D_{i\!-\!1}$. Initially $\D_0$
contains all terminal and Steiner edges. The adversary announces that
a given the Steiner edge $\{t_k,s_j\}$ is implicit by deleting it from
this domain $\D_{i\!-\!1}$.

We call a stacked edge {\em necessary} if it does not create a cycle
with edges that appear before it on the stack. Otherwise, it is called an {\em
unnecessary} edge. In order to prove the theorem, we first prove that
the adversary is able to maintain the following loop invariants.

\begin{itemize}
\item [$LI_1$:] Wrt $\D_{i\!-\!1}$, either $S_1$ or $S_2$ applies to each Steiner node
  $s_j$.
\begin{itemize}

\item [$S_{1}$:] At most one necessary explicit Steiner edge incident
to $s_j$ has been stacked by the algorithm and all steiner edges
incident to it are still in $\D_{i\!-\!1}$.

\item [$S_{2}$:] Exactly two necessary explicit Steiner edges are
incident to $s_j$ and each of the rest of the edges incident to $s_j$ has been
rejected, stacked as unnecessary edge, or removed by the adversary
causing it to be implicit.

\end{itemize}
\item [$LI_2$:] A relation $r\!+\!b\!+\!b' \geq n_t\!-\!c$ holds. 
\end{itemize}

We prove the loop invariants are maintained as follows.  Initially, no
edge has been seen. Therefore, $S_{1}$ applies to all Steiner nodes,
and $r = b = b' = 0$ and $c = n_t$, which results in $r\!+\!b\!+\!b'
\geq n_t\!-\!c$. Therefore, the base case clearly holds.
Now assume that the loop invariants hold at the beginning of $i^{th}$
iteration. The Figure~\ref{fig:mstp-stack-induction} depicts a
possible adversarial set $\D_{i\!-\!1}$.
Imagine that an algorithm considers an edge. No matter what type it
is, nothing changes if it is rejected by the algorithm. Hence, we
consider only acceptance cases.

\figc{1.5851in}{fig/mstp-stack-induction}{A possible situation at
  the beginning of the $i^{th}$ iteration.}
  {fig:mstp-stack-induction}

\bd
\i[Case 1:] The algorithm stacks a necessary terminal edge
  $D_i = \{t_k,t_k'\}$. The adversary, in turn, does nothing,
  yielding $\D_i = \D_{i\!-\!1}$. Since $D_i$ is a terminal edge, it
  does not affect $S_{1}$ or $S_{2}$. The $c$ decreases by one, $r$
  increases by one, and $b$ and $b'$ are unchanged. Hence, the
  relation $r\!+\!b\!+\!b' \geq n_t\!-\!c$ still holds.


\i[Case 2:] The algorithm stacks an explicit Steiner edge $D_i =
  \{t_{g},s_{j}\}$, which is the first stacked edge incident to
  $s_j$. The adversary does nothing, yielding $\D_i =
  \D_{i\!-\!1}$. The $s_j$ must have been of type $S_1$ and remains to
  be type $S_1$. Hence $b, b', r$, $c$, and $r\!+\!b\!+\!b' \geq
  n_t\!-\!c$ are unchanged.

\i[Case 3:] The algorithm stacks the second necessary and
  explicit Steiner edge $D_i = \{t_k, s_j\}$  incident to Steiner
  node $s_j$. The adversary, in turn, removes the rest of the unseen
  edges incident to $s_j$, yielding $\D_i \subset \D_{i\!-\!1}$. These
  removed edges become implicit edges. Moreover, $S_2$ now applies to
  $s_j$ instead of $S_{1}$, increasing $b$ by one. Since $D_i$
  is necessary, it does not create a cycle with previously stacked
  edges and hence $c$ decreases by 1. The $r$ and $b'$ are
  unchanged. Hence, the relation $r\!+\!b\!+\!b'\geq n_t\!-\!c$ is true.

\i[Case 4:] The algorithm considers an edge which creates a cycle with
  stacked edges. By definition, such an edge is called
  unnecessary. Whether the algorithm decide to stack or to reject it,
  the adversary does nothing, yielding $\D_i = \D_{i\!-\!1}$. Note $b$ and
  $c$ does not change, but $r$ or $b'$ may increase by one. Hence,
  the relation $r\!+\!b\!+\!b' \geq n_t\!-\!c$ still holds.

\i[Case 5:] The algorithm stacks a necessary and implicit Steiner edge
  $\{t_{k'},s_j\}$ without actually seeing it. If this edge is still
  in $\D_{i\!-\!1}$ then the adversary inform the algorithm that actually
  this edge is explicit in the actual input instance. It is just that
  the algorithm has not yet read this part of the input. This case can
  be handled by Case 2, 3, or 4. If the edge being accepted is not in
  $\D_{i\!-\!1}$, the adversary informs the algorithm that this is in fact
  an implicit edge and its weight is 3. In latter case, the adversary
  in turn does nothing, yielding $\D_i = \D_{i\!-\!1}$. Since the edge is
  implicit, it does not affect $S_1$ nodes. The $c$ decreases by one,
  $b'$ increases by one, and $r$ and $b$ are unchanged. Hence, the
  relation is still true.

\ed

\noindent
Based on the five cases above, we conclude that the loop invariants
are maintained.  When $c$ becomes 1, the adversary knows that the
terminal nodes are connected by the stacked edges into one component.
Hence, he knows that there is an expensive solution pushed on the
stack. The adversary at this point stops this first phase of the
game. He declares to the algorithm that the actual input instance
consists of the edges seen by the algorithm so far together with all
the edges remaining in $\D_i$.  The next task is to prove that this
instance contains a cheap optimal solution. The first step to
accomplish this is to note that at most $n_t\!-\!1$ Steiner nodes of
type $S_2$ connect the $n_t$ terminal nodes into one component.
Because there are $n_s \ge n_t$ Steiner nodes, the loop invariant
ensures us that there is at least one Steiner node remaining of type
$S_1$. All the edges incident to such a node have not ever been
deleted from $\D_i$ and hence all appear explicitly in the input. This
forms a $n_t$-star which in itself is an optimal solution of weight
$n_t$.

At the end of this first stage of the game, the algorithm still must
make decisions about the remaining data items in the input instance
(which according to the adversary will be those edges remaining in
$\D_i$). The algorithm may decide to stack them or decide to reject
them.  It does not actually matter to the adversary, because either
way these edges will be rejected at the very beginning of the pop
stage of the algorithm. The reason for this is that the adversary was
careful that there is an expensive solution previously pushed on the
stack and hence these remaining edges in $\D_i$ are not needed.

   % \figc{4.471in}{fig/mstp-2s-instance}{Two possible final
   % instances of the newly defined game. The optimal solution is the
   % $n_t$-star incident to $s_h$. Since there is another valid solution
   % stacked beneath the $n_t$-star, the algorithm cannot accept the
   % $n_t$-star.}{fig:mstp-2s-instance}

As the rest of the pop stage of the algorithm proceeds, we need to
prove which of the algorithm's stacked edges get forcefully accepted
and which get forcefully rejected. This happens in reverse of the
pushed order. Any edge labeled as unnecessary will be rejected when it
is popped. It formed a cycle with the edges already pushed on the
stack when it got pushed on and hence it will form the same cycle with
the edges still on the stack when it is popped. The one necessary
Steiner edge incident to a Steiner node of type $S_1$ will also be
rejected. All other edges incident to this Steiner node either was
initially rejected and not stacked or has already been popped and
rejected by the pop stage. Hence, this edge is not a part of a
remaining solution.  What will get forcefully accepted when popped
will be the ``edges'' forming the expensive solution. As they got
stacked by the algorithm these were needed to merge the connected
components of the terminal nodes together and hence are all needed for
the solution. Each terminal edge has weight 2.  There are two Steiner
edges incident to each Steiner node of type $S_2$, each with weight
1. Each implicit Steiner edges incident has weight 3.  Hence the cost
of this popped and accepted solution is $2 \cdot r + (1+1) \cdot b + 3
\cdot b' \ge 2 (r\!+\!b\!+\!b')$ which by the loop invariant is at
least $2(n_t\!-\!c)$ and by the termination condition is
$2(n_t\!-\!1)$. Above we showed how the cost of the optimal solution
is only $n_t$. Hence, we can summarize the competitive ratio to be
$\mathcal{R} = \frac{ALG}{OPT} \ge \frac{2(n_t\!-\!1)}{n_t}~=~2 -
\frac{2}{n_t}~=~2 - \bigO(\frac{1}{|V|})$. \epf


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{A $1\frac{1}{3}$ Priority Lower Bound given a Complete Graph}
\label{subsec:mstp-fixed}

Davis and Impagliazzo \cite{DI04} proved the first priority lower
bound for the MStT problem, where the approximation ratio is $1\frac{1}{4}$.
This result is still incomparable with the lower bounds of 2 given above because they give their results when the input graph must be a complete
{\em quasi bipartite} graph, meaning that there are no edges between the Steiner nodes, but all other edges are explicitly in the instance.
Playing with their cases further, we managed to improve their lower
bound to $1\frac{1}{3}$. 

Imposing that the instance must be a complete quasi bipartite graph makes proving a lower bound harder.  The adversary can no
longer simple delete an edge $\left<u,v\right>$, it must either
delete all the edges incident to the node $u$ or all those incident to
$v$. Although such a step $\D_i \subseteq \D_{i-1}$ is really a
reduction in the set of edges, we call this {\em the adversary
deleting the node $u$ (or $v$)}.

\tm{thm:mstp4over3} No adaptive priority algorithm 
can achieve better than $1\frac{1}{3}$ approximation for the MStT
problem even when restricted to complete quasi bipartite graphs in which the triangle inequality holds.
\etm

\pftm{thm:mstp4over3} The adversary initially constructs a set $\D_0$
shown in Figure~\ref{fig:mstp-fixed}.

\figc{0.9602in}{fig/mstp-fixed}{The adversarial set $\D_0$ and a bold
edge is assumed to be considered first by the algorithm. Each right of
$\D_0$ is the second adversarial set $\D_1 \subseteq \D_0$ reduced by the
adversary. The squared nodes are terminals and the circled ones are
Steiner.}{fig:mstp-fixed}

\bd \i[Case 1:] If the algorithm initially considers a Steiner edge,
by symmetry we can assume that it considers $D_1 = \{t_1,
s_1\}$. If the algorithm accepts the edge, the adversary declares that
the actual instance is this one edge, denoted $P^1_0$.  Note, it is a
complete graph as promised. Accepting this edge was a mistake, giving
the approximation ratio is $\mathcal{R} = \frac{ALG}{OPT} =
\frac{1}{0} \approx \infty$. If the algorithm rejects this edge, the
adversary gives the entire graph as the instance, denoted $P^2_1$. No
matter what future decisions are made, the best cost for the algorithm
is 4 whereas the optimal cost is by taking the three Steiner
edges. Therefore, the approximation ratio is $\mathcal{R} =
1\frac{1}{3}$.

\i[Case 2:] If the algorithm initially considers a terminal edge, by
symmetry we can assume that it considers $D_1 = \{t_1, t_2\}$. If
the algorithm accepts the edge, again the adversary gives the entire graph, $P^3_1$
again giving $\mathcal{R} = 1\frac{1}{3}$. If the algorithm rejects the
edge, the adversary removes all the remaining edges, shown as
$P^4_1$. In this case, the algorithm even fails to find a valid
Steiner tree.  \ed

\noindent
An arbitrary large lower bound can be obtained by having much bigger
weights on the terminal edges. This, however, violates the triangle
inequality. 
\epf 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\medskip
A concern with our above $1\frac{1}{3}$ result and Davis and
Impagliazzo \cite{DI04}'s $1\frac{1}{4}$ result is that only small
graphs, instances with at most four nodes, are considered. Because the
lower bound does not consider arbitrarily large graphs, it does not
prove that this error is multiplicative.  

   % \medskip
   % 
   % *** We could well delete this next section ****

\medskip

One feature of our $1\frac{1}{4}$ and their $1\frac{1}{3}$ result
is that it holds even when the algorithm knows a priori not necessarily which nodes and hence which edges are present in the instance, but what
the weight of each edge will be if it is present.
Though this does strengthen the result slightly, because it gives the algorithm more power and the adversary less,
the true motivation for this change is that it significantly simplifies the proof. When arbitrary weights are possible and the algorithm sorts the data items according to these weights in an arbitrary way, then it is hard for the adversary to keep track of which weights are still possible.

This motivates us to want to
prove a lower bound with fixed weights, arbitrarily large $n$, and a
complete graph. It seems, however, that this gives too much power to
the algorithm. We now outline a strange and
unfair algorithm that uses tricks to learn the input instance and then
uses its unbounded computational power to obtain what we conjecture to
be a near optimal solution.

\cj{thm:mstp-epsilon}
A priority algorithm can achieve a $1 +
O(\frac{1}{k})$ upper bound for the MStT problem with the 
weights on each possible edge is known a priori but which nodes in the graph are not.
\ecj

\noindent
{\it Proof Sketch for Conjecture~\ref{thm:mstp-epsilon}} Because the
weights are fixed and the graph is complete on the nodes that are in
the graph, to learn the entire instance, the algorithm need only learn
which nodes are in the instance.  To learn this, the algorithm
need only to see one edge incident to each node.  An algorithm can do
this by asking for and reject the most expensive edge incident to each
node.  One has to be a little careful the one does not disconnect the
graph. But that aside, we conjecture that there exists an nearly
optimal solution not containing any of these rejected edges. The
algorithm uses its unbounded computational power to find such a near
optimal solution.  $\blacksquare$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Upper Bounds} \label{sec upper}

This section provides the upper bound for four variations of the
Minimum Steiner Tree Problem on four variations of the priority model.
We start by considering the most general version of the problem, i.e.\
there may be edges between the Steiner nodes and the triangle
inequality may not hold. Kou, Markowsky and Berman \cite{KMB} give a
well known 2-approximation algorithm.  Given a graph $G$, let $G^c_R$
denote the metric completion of $G$ on the terminal nodes, namely for
every pair of terminal nodes $u, v \in R$, the cost of edge $\{u,v\}$
in $G^c_R$ is the length of the shortest path from $u$ to $v$ in
$G$. Let $MST(G^c_R)$ denote a Minimum Span Tree of $G^c_R$. Let
$Alg(G)$ denote the union over all terminal edges $\{u,v\} \in
MST(G^c_R)$ of a shortest path in $G$ from $u$ to $v$ (if necessary
remove edges in order to break cycles).  The weight of this Steiner
tree is at most twice the optimal Steiner $MStT(G)$. See
\rfig{fig:upper1} for an instance for which there is a factor of two
loss. The optimal has weight $|R|$ consisting of the star branching
from the single Steiner node to each terminal node. The solution
$Alg(G)$ has weight $2(|R|-1)$ consisting of the path through the
terminal nodes.  \rfig{fig:upper} gives a
more complex example.  Part of the metric completion $G^c_R$ of $G$ is
given on the bottom right. Its minimal spanning tree is in bold. The
solution $Alg(G)$ consists of every edge in $G$ except for
$\{a,b\}$. ($\{b,v\}$ is not bold in order to demonstrate something
else. This solution is in fact optimal.

\figwc{3.5in}{fig/mstt1}{An instance for which there is a factor of two
loss.} {fig:upper1}

\tm{tm MST}
$Alg(G) \le 2 MStT(G)$
\etm

\pftm{tm MST} Let $T$ be a Minimum Steiner Tree of the instance graph
$G$, i.e.\ spanning all the terminal nodes $R$.  From this, form a
traveling salesman tour, $TST$, in $G$ that visits every node in $R$
by embedding the tree $T$ as a wall in the plane, placing ones left
hand on the wall, and tracing the outside of it until you return.
Because each edge is visited twice, $w(TST) = 2 w(MStT(G))$.
\rfig{fig:upper} shows an example of $T$ in bold, $TST$ in curve, and
$SG$ in a dotted line.  Here $SG$ is a spanning graph of $G^c_R$
formed from $TST$ by including edge $\{u,v\}$ if $v$ is the next
terminal node visited after $u$ in this tour. Because the weight on
$G^c$ edges are the length of the shortest paths in $G$, we have that
$w(SG) \le w(TST)$.  From this, form a spanning tree $ST$ of $G^c_R$
by deleting enough edges to break all cycles.  This gives,
$w(MST(G^c_R)) \le w(ST) \le w(SG)$.  The algorithm produces a Steiner
tree $Alg(G)$ such that $w(Alg(G)) \le w(MST(G^c_R))$.  \epf

\figwc{6in}{fig/mstt2}{An instance $G$.  The key edges in the metric
  completion $G^c_R$ with its minimum spanning tree in bold is used to
  demonstrate the 2-approximate minimal Steiner tree algorithm. The
  resulting Steiner tree in $G$ (which is optimal) consists of the
  bold edges plus $\{b,v\}$. $T$, $TST$, and $SG$ used in the proof of
  correctness of this algorithm is also given.  The graph $G$ is
  partitioned into $N(u)$ and $G'^c_R$ with its minimum spanning tree
  in bold is given as done in the Mehlhorn algorithm.  The edges bold
  in $G$ are those pushed on the stack by our algorithm when $\ell =
  10$ just before the edge $\{a,b\}$ is considered. It is used to
  demonstrate the proof of correctness of our algorithm.}{fig:upper}

\medskip
The obvious way to find the metric completion $G^c_R$ is to perform
Dijkstra's algorithm rooted at each of the terminal nodes, hence
requiring time $|R| \times \bigO(|V| \log
|V|+|E|)$.\footnote{Dijkstra's algorithm can be sped up from
$\bigO(|E|\log |V|)$ to $\bigO(|V|\log |V|+|E|)$ by using a {\em
fractal} data base \cite{fractal} instead of a heap for the priority
queue.} Mehlhorn \cite{WWW86,W86,M88} finds a $\bigO(|V| \log
|V|+|E|)$ implementation of this algorithm by performing one
Dijkstra's algorithm rooted at an axillary node $s_0$ connected to
each of the terminal nodes.  This is done in order to partition the
nodes into $\{N(u)\ |\ u \in R\}$, where $N(u)$ is the set of nodes
which are closer to the terminal node $u$ than to any other terminal
node.  \rfig{fig:upper} shows an example instance $G$ partitioned into
these neighborhoods. Mehlhorn then does a second pass through all the
edges of the graph in order to form a graph $G'^c_R$ consisting of
pairs of terminal nodes $\{u,v\}$ that are close enough so that their
neighborhoods $N(u)$ and $N(v)$ are connected by a single edge
$\{a,b\}$. The weight of an edge $\{u,v\}$ in $G'^c_R$ is the weight
of the minimum path between $u$ and $v$ that includes only nodes from
$N(u)$ and $N(v)$.  The figure shows the corresponding
graph $G'^c_R$.  Note that the weight 19 of $\{x_1,x_3\}$ is larger
than the weight 8 of the minimum $x_1 x_3$-path. Despite these
differences between $G'^c_R$ and $G^c_R$, they prove that a minimum
spanning tree of $G'^c_R$ is also a minimum spanning tree of
$G^c_R$. More over, they proof that for each edge $\{u,v\}$ in
$MST(G'^c_R)$, the found path between $u$ and $v$ in $G$ is of minimum
weight. Hence, Mehlhorn can complete the algorithm by finding
$MST(G'^c_R)$ and returning these paths.

In order to fit their algorithm into the adaptive priority stack
model, we need to change their implementation in a few ways.  They
find the edge $\{a,b\}$ connecting neighborhoods $N(u)$ and $N(v)$
during a second pass. We are not allowed such a second pass.  Some
such edge $\{a,b\}$ can easily be found during the first pass as the
neighborhoods $N(u)$ and $N(v)$ merge. However, we show how to
slightly modify the Dijkstra priority on the edges so that the
connecting edge $\{a,b\}$ first found is one that gives a shortest
path from $u$ to $v$. Unlike them, we are not able to compute the
minimum spanning tree of $G'^c_R$ in a separate phase. Our
modification on $\{a,b\}$'s priority also ensures that the pairs of
terminal nodes $\{u,v\}$ will be connected in the order mirroring the
order that edges $\{u,v\}$ are added to $MST(G^c_R)$ by the minimum
weight greedy algorithm. Their algorithm needs a final stage that
collects together the shortest $uv$-paths for each edges $\{u,v\} \in
MST(G'^c_R)$ and breaks any cycles.  Instead, our algorithm pushes on
the stack all the edges in the shortest paths trees expanding out from
the terminal nodes.  We prove that the pop phase defined for the stack
model automatically deletes all unnecessary edges leaving only the
edges in $Alg(G)$.

\tm{upper no triangle} There is a 2-approximate adaptive priority
stack algorithm solving the MStT problem even when there may be edges
between the Steiner nodes and the triangle inequality may does not
hold.  \etm

\noindent
This upper bound together with the lower bound in \cite{DI10} for
$st$-connectivity proves that the adaptive priority stack model is
incomparable with the fully adaptive priority branching tree (pBT)
model.

\medskip
\pftm{upper no triangle} Because our algorithm wants to find a short
path between every pair of terminal nodes $u$-$v$, it uses this
Dijkstra's algorithm to simultaneously expand a shortest paths tree
around each terminal node $u \in R$. It is easier to visualize the
synchronizing of these expansions by as having a parameter $\ell$
slowly increase.  For each edge $\{a,b\}$ and terminal node $u$,
define $\ell_{\left<\{a,b\},u\right>} $ to be the length of the
shortest path from $u$ that includes the edge $\{a,b\}$.  When $\ell$
reaches this value, this edge will be added to the tree expanding out
of $u$, assuming that it has not already been added elsewhere.
Similarly, define $\ell_{\left<\{a,b\},\{u,v\}\right>} $ to be half
the length of the shortest path from $u$ to $v$, if the edge $\{a,b\}$
contains this half way point.  When $\ell$ reaches this value, this
edge, if not already used, will be used to merge the tree expanding
from $u$ and that expanding from $v$.  For example, in
\rfig{fig:upper} when $\ell = {5 \over 2}$, the tree expanding from
terminal node $x_1$ merges with that expanding from $x_2$ by having
the edge $\{d,e\}$ added. At this same moment, the edge $\{x_1,x_2\}$
is added to the minimal spanning tree of the metric completion graph
$G^c_R$.  Define $\ell_{\{a,b\}} = \min( \min_{u \in R}
\ell_{\left<\{a,b\},u\right>}, \min_{u,v \in R}
\ell_{\left<\{a,b\},\{u,v\}\right>} )$ to be the value for the
parameter $\ell$ at which the edge $\{a,b\}$ is first considered in
one of these ways.

This is implement in the adaptive priority stack model simply by
choosing next the unseen edge with the smallest $\ell'_{\{a,b\}}$
value. Here $\ell'_{\{a,b\}}$ is $\ell_{\{a,b\}}$ if all the other
edges in that path up to edge $\{a,b\}$ have already been seen so that
the algorithm can know the value $\ell_{\{a,b\}}$.

When the edge $\{a,b\}$ is considered, it is pushed onto the stack if
it does not creates a cycle with the previously pushed edges,
otherwise, it is rejected.  Let $MST(G^c_R)$ denote the minimal
spanning tree of $G^c_R$, where ties are broken in the same way as
done in this algorithm.  \rlm{lm MST} proves that for each edge
$\{u,v\} \in MST(G^c_R)$, the edges pushed on the stack by our
algorithm contains a shortest path from $u$ to $v$, i.e.\ a path with
weight equal to that of edge $\{u,v\} \in G^c_R$. Because the edges
$\{u,v\} \in MST(G^c_R)$ span the terminal nodes, so does the union of
these shortest paths from $u$ to $v$. Being a tree, the edges in this
union and no edges outside it are kept when the stack pops, i.e.\ the
pushed edges connecting the unnecessary Steiner nodes are deleted.
Hence, the weight of the Steiner tree returned by this algorithm is at
most that of $MST(G^c_R)$, which by \rtm{tm MST} is at most twice the
optimal $MStT(G)$.  \epf

\lm{lm MST} Let $MST(G^c_R)$ denote the minimal spanning tree of
$G^c_R$, returned by the standard minimum weight greedy algorithm
where ties are broken in the same way as done in the \rtm{upper no
triangle} algorithm.  For each edge $\{u,v\} \in MST(G^c_R)$, the
edges pushed on the stack by contains a shortest path from $u$ to $v$.
For example, this true for $\{x_1,x_2\}$ in \rfig{fig:upper} but not for
for $\{u,v\}$.  \elm

\pflm{lm MST} We prove the contra-positive.  Denoted by $P_{\{u,v\}}$
the shortest path between terminal nodes $u$ and $v$ that would be
found by our algorithm if these were the only nodes from which
shortest paths trees expanded.  Suppose there is an edge $\{a,b\} \in
P_{\{u,v\}}$ that is not pushed on the stack. We will prove that the
when the $MST(G^c_R)$ algorithm considers the edge $\{u,v\}$, it is
not accepted. \rfig{fig:upper} was designed in particular to help
with this proof.

The reason edge $\{a,b\}$ is not pushed on the stack when it was
examined is because it created a cycle with already pushed edges.  Let
$P_{\{a,b\}}$ denote this pushed $ab$-path.  Label each edge $\{c,d\}$
in $P_{\{a,b\}}$ with the terminal node $x_i$ at the root of the
shortest paths tree that added the edge.  If $\{c,d\}$ merged trees
rooted at $x_i$ and $x_{i+1}$ then give the edge either label. Because
these label appear contiguously, we can let $\left<x_1,\ldots,x_r
\right>$ denote the sequence of distinct terminal nodes labeling the
edges in $P_{\{a,b\}}$.  Let $P^c$ denote the $uv$-path
$\left<u,x_1,\ldots,x_r,v \right>$ in $G^c_R$.  For each
$\{x_i,x_{i+1}\} \in P^c$, we will show that $w^c_{\{x_i,x_{i+1}\}}
\le w^c_{\{u,v\}}$, giving that the $MST(G^c_R)$ algorithm considers
the edge $\{x_i,x_{i+1}\} $ before $\{u,v\}$.  This ensures that when
the $MST(G^c_R)$ algorithm considers the edge $\{u,v\}$, it does not
accept it because it forms a cycle with the edges that it has already
accepted. This completes the contra-positive proof of the lemma.

Let $\{c,d\}$ and $\{d,e\}$ be consecutive edges $P_{\{a,b\}}$ that
are labeled respectively with $x_i$ and $x_{i+1}$.  Note that
$w^c_{\{x_i,x_{i+1}\}} \le w(P_{\{x_i,d\}}) + w(P_{\{x_{i+1},d\}})$
because by definition $w^c_{\{x_i,x_{i+1}\}}$ is the weight of the
shortest path from $x_i$ to $x_{i+1}$ in $G$ and $P_{\{x_i,d\}} +
P_{\{x_{i+1},d\}})$ is such a path.  By the label of $x_i$ on the edge
$\{c,d\}$, we know that either $\{c,d\}$ was pushed to be a part of
the path from $x_i$ to $d$ in the shortest paths tree rooted at $x_i$
or was pushed to extend this path. Either way, we have that
$w(P_{\{x_i,d\}}) \le \ell_{\{c,d\}}$.  Next we have $\ell_{\{c,d\}}
\le \ell_{\{a,b\}}$ because the edge $\{c,d\}$ was pushed by our
$MStT(G)$ algorithm before $\{a,b\}$ was.  We have that
$\ell_{\{a,b\}} = \min( \min_{u' \in R}
\ell_{\left<\{a,b\},u'\right>}, \min_{u',v' \in R}
\ell_{\left<\{a,b\},\{u',v;\}\right>} ) \le
\ell_{\left<\{a,b\},\{u,v\}\right>} = {1 \over 2} w(P_{\{u,v\}}) = {1
  \over 2} w^c_{\{u,v\}}$. Similarly, $P_{\{x_{i+1},d\}}) \le {1 \over
  2} w^c_{\{u,v\}}$, completing the result that $w^c_{\{x_i,x_{i+1}\}}
\le w^c_{\{u,v\}}$ and in doing so completing the proof.  \epf

\medskip
Though \cite{M88} has already implemented their MStT algorithm to run
in time $\bigO(|V|\log |V|+|E|)$, it is interesting to see 
the adaptive priority stack model can also do it in this time. 

\lm{lm time} As stated, our implementation of the algorithm requires
time $\bigO(|E|\log |E|)$, but another small change will decrease the
time back to $\bigO(|V|\log |V|+|E|)$.
\elm

\pflm{lm time} Dijkstra's algorithm can be sped up from $\bigO(|E|\log
|V|)$ to $\bigO(|V|\log |V|+|E|)$ by using a {\em fractal} data base
\cite{fractal} instead of a heap for the priority queue. Removing the
minimum data item still takes $\bigO(\log |V|)$ time but decreasing
the priority value $\ell$ of an item now only takes $\bigO(1)$
amortized time.  Dijkstra, using node data items, removes the minimum
item $|V|$ times and decreases a priority $2|E|$ times, giving the
stated times.  \rtm{upper no triangle}, using edge data items, removes
the minimum item $|E|$ times, giving the old Dijkstra time
$\bigO(|E|\log |E|)$. To get the improved time, the adaptive priority
stack model needs to have both node data items and edge data items.
The node data items contain pointers to the adjacent edges and the
edge data items contain pointers to the adjacent nodes. The node data
items are taken as the trees grow.  The data item $\{a,b\}$ is taken
only as the tree growing from terminal node $u$ to node $a$ merges
with that growing from $v$ to $b$.  \epf



   %% we switch partially to node data items.
   %% 
   %% Identical to Dijkstra's algorithm the new implementation maintains
   %% shortest paths tree(s) to the set of already reached nodes
   %% $S$. Instead of a single node $s_0$, $S$ initially contains all the
   %% terminal nodes. Identical to Dijkstra's algorithm, it maintains a
   %% priority queue of unseen nodes. In order to handle the merging of the
   %% shortest paths trees from different terminal nodes, the implementation
   %% also includes in the priority queue the unseen edges $\{a,b\}$.  When
   %% a node $a$ is added to $S$, all nodes and edges adjacent to $a$ have
   %% their priority values updated. The priority value of a node $b$ is
   %% $\ell_b = \min_{u \in R} \min_a \ell_{\left<\{a,b\},u\right>}$, where
   %% as in \rlm{upper implement} $\ell_{\left<\{a,b\},u\right>}$ is the
   %% length of the shortest path from terminal node $u$ through the
   %% shortest paths tree to the reached node $a \in S$ plus the length
   %% of the additional edge $\{a,b\}$.  The priority value of an edge
   %% $\{a,b\}$ is $\ell_{\{a,b\}} \min_{u,v \in R}
   %% \ell_{\left<\{a,b\},\{u,v\}\right>}$, where as in \rlm{upper
   %% implement} $\ell_{\left<\{a,b\},\{u,v\}\right>}$ is half of the length
   %% of the shortest path from $u$ to $v$ when both $a$ and $b$ are in $S$.
   %% 
   %% When the next data item in the priority queue is the edge $\{a,b\}$,
   %% it means that the tree contain $a$ rooted at $u$ is merging with the
   %% tree containing $b$ rooted at $v$. Running in parallel is a minimum
   %% spanning tree algorithm for $G^c_R$. The terminal nodes $R$ are
   %% partitioned into connected components using a set union-find data
   %% structure. In amortized $Ackermann^{-1}(|R|)$ time, this data
   %% structure is able to tell us whether or not this next shortest edge
   %% $\{u,v\}$ creates a cycle. If not it is added to
   %% $MST(G^c_R)$. Included in the $\{u,v\}$ data item is a pointer to the
   %% edge $\{a,b\}$ that completed the shortest path from $u$ to $v$.
   %% 
   %% The computation ends when the edges in $MST(G^c_R)$ span the graph
   %% $G^c_R$.  The next phase of the algorithm needs to mirror the popping
   %% of the stack keeping only the edges necessary for the $MStT(G)$
   %% solution. This has already been accomplished implicitly. When one
   %% wants the shortest path between the terminal nodes $u$ and $v$, one
   %% starts at the edge $\{u,v\}$ in $MST(G^c_R)$. This leads to the edge
   %% $\{a,b\}$.  This leads to the nodes $a$ and $b$. From each of these,
   %% one can follow the path of parent nodes back to the roots $u$ and $v$.
   %% 
   %% The timing of this implementation is as follows.  It still requires at
   %% most $\bigO(|E|)$ decreases of the $\ell$ for data items in the
   %% priority queue.  When a fractal data base is used, this requires only
   %% $\bigO(1)$ amortized time each. The number of minimum nodes removed
   %% from the priority queue is still at most $|V|$, but now there are
   %% $|E|$ edges in the priority queue as well. However, only $|N|-1$ of
   %% them are removed before the $MST(G^c_R)$ spans the graph $G^c_R$
   %% causing the algorithm to stop. Hence, the running time is
   %% $\bigO(|V|\log |E|+|E|) = \bigO(|V|\log |V|+|E|)$ as stated.
   %% \epf

\medskip
In order to better understand both the minimum Steiner tree problem
and variations of the priority model, we will now consider upper bounds
for three restrictions of the problem on three more variations of
model.  The first restriction requires that there are no edges between
the Steiner nodes, i.e.\ the graph is {\em quasi bipartite}.  The
following algorithm is surprisingly simple and does not require
reordering the edges each iteration.

\tm{upper no triangle fixed}
There is a 2-approximate {\bf fixed stack} priority algorithm solving the
MStT problem when there are no edges between the Steiner nodes, even
when the triangle inequality does not hold.
\etm

\pftm{upper no triangle fixed}
The push phase of the stack algorithm pushes a minimum spanning tree,
$MST(G)$, of the entire graph $G$. 
If a Steiner node only has one adjacent edge pushed, then this edge is
not necessary for spanning the terminal nodes and this edge is deleted
in the pop phase of the algorithm. Let $Alg$ denote the popped and
accepted edges. 
Let $S$ denote the set of Steiner nodes that are used, i.e.\ those
with degree at least two in $Alg$,
and $\overbar{S}$ the remaining Steiner nodes. For each Steiner node
$s$, let $e_s$ denote the cheapest edge adjacent to $s$ and $w_s$ its
weight. Note this edge goes to a terminal node because there are no
edges between the Steiner nodes.
Because each $s \in S$ has degree at least two in $Alg$, we have that
$2 \sum_{s \in S} w_s \le w(Alg)$.
The algorithm first pushes $Alg \cup \bigcup_{s \in \overbar{S}} e_s$
and hence this is a minimum spanning tree of $G$.
$MStT(G)$ spans the terminal nodes and hence $MStT(G) \cup \bigcup_{s
  \in S \cup \overbar{S}} e_s$ spans all of $G$.
This gives that $w(Alg)  + \sum_{s \in \overbar{S}} w_s \le 
w(MStT(G)) + \sum_{s \in S \cup \overbar{S}} w_s$ or simplified to 
$w(Alg) \le 
w(MStT(G)) + \sum_{s \in S} w_s  \le 
w(MStT(G)) + {1 \over 2} w(Alg)$ and hence
${1 \over 2} w(Alg) \le 
w(MStT(G)) $. \epf

\medskip
This previous algorithm sorts the edges according to edge weights.
Hence, if all the edges have the same weight, then any order will
suffice.

\tm{upper online}
There is a 2-approximate {\bf online stack} priority algorithm solving the MStT
problem when there are no edges between the Steiner nodes
and the weight of every edge included is one.
\etm

\noindent
This upper bound together with the lower bound in \rtm{lower priority}
proves that the online stack model is incomparable with the adaptive
priority model.

The above algorithms used the popping of the stack to get rid of the
edges that are not in the required shortest paths.  This is necessary.
Davis and Impagliazzo in \cite{DI?,DI10} shows that when each data
item contains an edge, then though an adaptive priority algorithm
without a stack can accept the shortest paths tree, (even when it is
allowed to branch to a subexponential width), it cannot be designed to
accept a shortest path from $s$ to $t$ (without accepting unneeded
edges).

Trivially, however, if shortest paths, i.e.\ the weights of the edges
in $G^c_R$, are given as part of the input then the 2-approximation of
the minimal Steiner tree problem is easy.

\tm{upper triangle} There is a 2-approximate {\bf fixed no-stack} priority algorithm
solving the MStT problem when the triangle
inequality holds and the subgraph on the terminal nodes is complete.
\etm

\pftm{upper triangle}
By the triangle inequality assumption, the subgraph on the terminal
nodes is $G^c_R$. 
Hence, finding a minimum spanning tree, $MST(G_R)$, of this subgraph
gives a 2-approximation to $MStT(G)$.
$MST(G_R)$ can be found using the standard greedy algorithm. Sort the
terminal edges by weight and accept them if they don't form a cycle. 
\epf



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{thebibliography}{99}

\bibitem{ABBIMP05}
{\sc M.\ Alekhnovich, A.\ Borodin, J.\ Buresh-Oppenheim, R.\ Impagliazzo, A.\ Magen, and T.\ Pitassi} (2005)
Toward a model for backtracking and dynamic programming,
{\it IEEE Conference on Computational Complexity}.



\bibitem{BCM05}
{\sc A.\ Borodin, D.\ Cashman, and A.\ Magen}, (2005)
How well can primal-dual and local-ratio algorithms perform?,
{\it International Colloquium on Automata, Languages and Programming (ICALP)}.



\bibitem{BNR02}
{\sc A.\ Borodin, M.\ Nielsen, and C.\ Rackoff}, (2002)
(Incremental) Priority algorithms,
{\em Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms}. 



\bibitem{Cas05}
{\sc D.\ Cashman}, (2005)
Approximate Truthful Mechanisms for the knapsack problem, and negative results using a stack model for local ratio algorithms,
{MSc Thesis, University of Toronto}.



\bibitem{DI04}
{\sc S.\ Davis and R.\ Impagliazzo} (2004)
Models of greedy algorithms for graph problems,
{\it Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms}.


% \bibitem{DI10}
{\sc S.\ Davis and R.\ Impagliazzo} (2010)
???????????????


\bibitem{Kwo08}
{\sc H.\ Kwon}, (2008)
Improved results on models of greedy and primal-dual algorithms,
{MSc Thesis, York University}.



\bibitem{Vaz01}
{\sc V. Vazirani} (2001).
{\em Approximation Algorithms}.
Springer.



\bibitem{GHNP00}
{\sc C. Gr\"{o}pl, S. Hougardy, T. Nierhoff, and H. Pr\"{o}mel},
Approximation Algorithms for the Steiner Tree Problems in Graphs,
{\em Steiner Trees in Industries},
editors: D. Z. Du and X. Cheng,
Kluwer.



\end{thebibliography}


\end{document}



