% -*- Tex -*- macros for no-fill, built on Plain
\newenvironment{code}{\samepage \vskip 0.1in \tt\nofill}{\endnofill \vskip
0.1in}
\newenvironment{tightcode}{\samepage \tt\nofill}{\endnofill}
\catcode`\@=11\relax % allow @ in macro names
% a simple no-fill, used as
%
% \nofill
% Here is some no-fill text.
% This line starts with three spaces.
% This is the last line. It has embedded spaces which will appear.
% \endnofill
%
% You might want to switch to a fixed-width font when you use
% these macros.
\def\nofill {%
\begingroup
% spaces made active so they can be tested for at start of lines
% and so multiple spaces aren't collapsed to one.
\obeyspaces
% nofill via every line a par; if spaces start next line
% we do a \noindent to make sure a par gets started.
\parskip=\z@
\parindent=\z@
\let\p@r=\par
\def\par{\p@r \ifspacenext{\noindent}{}}%
\obeylines}
\def\endnofill{
\endgroup}
% \ifspacenext is used as:
% \ifspacenext {<true tokens>}{<false tokens>}
% It executes the true tokens if
% the next character is an active space, the false tokens
% otherwise. The same technique can be used to check for any
% character, not just active space.
% You can NOT nest uses of \ifspacenext!
% get a token which is \ifx-equal to active space, so we can test
% for it
{\obeyspaces\global\let\sp@ce= \relax}
\def\ifspacenext #1#2{%
\def\truet@ks{#1}%
\def\falset@ks{#2}%
\futurelet\next\ifsp@cenext}
\def\ifsp@cenext {%
\ifx\next\sp@ce \truet@ks \else \falset@ks \fi}
\catcode`\@=12\relax % make @ inaccessible again
--%--multipart-mixed-boundary-1.481.1043716445--%
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
Content-Description: ascii text
Content-Disposition: attachment; filename="sol.tex"
\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epic}
\usepackage{eepic}
\usepackage{psfig}
\input{code}
\newtheorem{statement}{~~~(\hspace*{-4pt}}[section]
\newcommand{\Xomit}[1]{}
\newcommand{\proof}[1]{
{\noindent {\it Proof.} {#1} \rule{2mm}{2mm} \vskip \belowdisplayskip}
}
\newcommand{\rf}[1]{
%%{{\hspace*{-8pt} (\ref{#1}) \hspace*{-8pt}}}
{{\hspace*{-6pt} (\ref{#1}) \hspace*{-6pt}}}
}
\def\stm{\hspace*{-5pt}{\bf )}~~}
\newcommand{\prevs}[2]{
{\vskip 0.1in \noindent {\em Proof of \rf{#1}.} {#2} \rule{2mm}{2mm}
\vskip \belowdisplayskip}
}
\newcommand{\prevproof}[2]{
{\vskip 0.1in \noindent {\em Proof of {#1}.} {#2} \rule{2mm}{2mm}
\vskip \belowdisplayskip}
}
\newcommand{\St}[1]{
\begin{itemize} \item {{#1}} \end{itemize}
}
\newcommand{\Pa}[1]{
\begin{quote} {\bf ($\dagger$)} {#1} \end{quote}
}
\newcommand{\Pp}[1]{
\begin{quote} {\bf $\triangleright$} {#1} \end{quote}
}
\newcommand{\xhdr}[1]{
\subsection*{#1}
}
\newcommand{\kth}[1]{
{{#1}^{\rm th}}
}
\newcommand{\cel}[1]{
{\lceil {#1} \rceil}
}
\newcommand{\flr}[1]{
{\lfloor {#1} \rfloor}
}
\def\sneq{{\tiny \mbox{$\neq$}}}
\def\subsetneq{\ \lower.5ex\hbox{$\stackrel{\subset}{\sneq}$}\ }
\newcommand{\topmatter}[2]{
\setlength{\fboxrule}{.5mm}\setlength{\fboxsep}{1.2mm}
\newlength{\boxlength}\setlength{\boxlength}{\textwidth}
\addtolength{\boxlength}{-4mm}
\begin{center}\framebox{\parbox{\boxlength}{\bf
Notes on {#1} \hfill {#2} \\ %% Title and Date
Jon Kleinberg and \'Eva Tardos \hfill
}}\end{center}
\vspace{5mm}
}
%%General
\def\ve{{\varepsilon}}
\def\gap{0.2in}
%%stable
\def\GS{{G-S}}
%%greedy
\def\O{{\cal O}}
%%divc
\def\ms{{\sc Mergesort}}
\def\qs{{\sc Quicksort}}
%%dp
\def\seq{{\sigma}}
\def\O{{\cal O}}
\def\P{{\cal P}}
\def\L{{\cal L}}
\def\opt{{OPT}}
\def\v{{value}}
%%flow
\def\O{{\cal O}}
\def\P{{\cal P}}
\def\L{{\cal L}}
\def\opt{{OPT}}
\newcommand{\into}[2]{
{#1}~{\rm into}~{#2}
}
\newcommand{\outof}[2]{
{#1}~{\rm out~of}~{#2}
}
\newcommand{\infl}[2]{
{#1}^{\rm in}({#2})
}
\newcommand{\outfl}[2]{
{#1}^{\rm out}({#2})
}
\def\Re{{\bf R}}
\def\v{{\nu}}
\def\bottle{{\tt bottleneck}}
\def\augment{{\tt augment}}
\def\ffinal{{\overline{f}}}