\documentstyle [11pt]{article}
\setlength{\parskip}{2 ex}
\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{9.5 in}
\setlength{\textwidth}{6.5 in}
\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}
\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\ceiling}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}

\newtheorem{defi}{Definition}[section] % Specify Definition
\newtheorem{problem}[defi]{Problem}      % Specify Lemma


\begin{document}
{\large
\noindent
Algorithms Core 15-750 \hfill PROBLEM SET \# 4 \hfill Spring 1999
\begin{center}
DUE: 1:00PM Wednesday March 17 1999 \\
\end{center}}

\section{The off-line $k$-server problem}

In the $k$-server problem we have an edge-weighted graph $G$ and $k$
servers each server is located at a node of the graph, we may have
more than one server at a node. At each time interval we get a request
from a subset of $s \leq k$ nodes of $G$ for a server. We must move
$s$ servers to each node that request a server.
We may also move other servers to new nodes in anticipation of later
requests.
The cost to move a
server from node $v$, were it is, to a new node $w$ is equal to the
min-cost path from $v$ to $w$ in $G$. In the off-line version of the
problem we are given all the request ahead of time we must simply
find the min-cost strategy to handle all the request at the requested
times.

\begin{problem}
Show how to reduce the off-line $k$-server problem to a min-cost
max-flow problem of size at most $O(n \cdot t)$ nodes and $O(n^2 \cdot
t)$ edges.
\end{problem}


\section{Maximum Flow for Negative Capacities}

In lecture we considered the case when all capacities are
nonnegative. Suppose we would like to find a maximum flow where the
flow on some edge $(u,v)$ is in the interval $[2,3]$, that is, the flow is at
least 2 but no more than 3. We can model this by setting the capacity
of $(u,v)$ to 3 and the capacity of $(v,u)$ to $-2$. 

\begin{problem}
Show how to reduce the problem of maximum flow with possibly negative
capacities to two maximum flow problems both with nonnegative capacities.
\end{problem}

\section{Maximum Planar Flow}

In this problem we consider the Max-Flow problem where the flow graph
is planar.  We first consider a simpler problem, we say that $G$ is a
{\bf circulation graph} if it has arc capacities $c$, in general $c$
may be negative. A circulation graph has no source or sink.  A
circulation of $G$ is a feasible flow on $G$.


A natural dual problem is finding potential functions.  A {\bf
potential graph} is a graph $G=(V,E)$ plus assignment of a weight
$w(e)$ to each arc of $G$, in general, the weights may be negative. A
function $p$ which assigns a real value to each node of $G$ is a {\bf
potential function} for $G$ if $w(u,v) \geq p(v) - p(u)$.


We first show there is a very nice relationship between flows in $G$
and potential functions on $G^*$ the geometric dual of $G$. Given an
arc  $e$ in $G$ the dual of $e$, denoted $e^*$ is the arc in $G^*$
from the face right of $e$ to the face left of $e$. 

\begin{problem}\label{dual}
Show how that a planar circulation graph $G$ has a circulation if
and only if the dual $G^*$ has a potential function, where $w(e^*) =
c(e)$.
\end{problem}

\begin{problem}
Show how to find a maximum flow in a planar flow graph in $O(n \log n)$
time when the capacities are nonnegative and the only source and only
sink lie on the same face.
\end{problem}



\begin{problem}
Show how to find a flow of some fixed size in a planar flow graph in
$O(n^{1.5})$ time when there is only one source and only one sink.
\end{problem}

You may use the fact that single source shortest paths can be
found in a planar graph in $O(n^{1.5})$ time. 
  

\section{Making a Palindrome}

Suppose we have $n$ words $W$ where the longest word has length $l$.
Give an $O(l^2 n^2)$ time algorithm to determine if we can form a
palindrome using words in $W$. You are allowed to uses the same word
more than once.

    
Hint: Try solving this problem on your own. But if after some time you
have not found a solution come by and we can give you a hint.


\end{document}
