\documentclass[10pt]{article}

\usepackage{epsfig}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amstext}
\usepackage{amscd}
\usepackage{amsmath}
\usepackage{xspace}
\usepackage{theorem}
\usepackage{float}

%\usepackage{layout}% if you want to see the layout parameters
                     % and now use \layout command in the body

% This is the stuff for normal spacing
\makeatletter
 \setlength{\textwidth}{6.5in}
 \setlength{\oddsidemargin}{0in}
 \setlength{\evensidemargin}{0in}
 \setlength{\topmargin}{0.25in}
 \setlength{\textheight}{8.25in}
 \setlength{\headheight}{0pt}
 \setlength{\headsep}{0pt}
 \setlength{\marginparwidth}{59pt}

 \setlength{\parindent}{0pt}
 \setlength{\parskip}{5pt plus 1pt}
 \setlength{\theorempreskipamount}{5pt plus 1pt}
 \setlength{\theorempostskipamount}{0pt}
 \setlength{\abovedisplayskip}{8pt plus 3pt minus 6pt}
 \setlength{\intextsep}{15pt plus 3pt minus 6pt}

 \renewcommand{\section}{\@startsection{section}{1}{0mm}%
                                   {2ex plus -1ex minus -.2ex}%
                                   {1.3ex plus .2ex}%
                                   {\normalfont\Large\bfseries}}%
 \renewcommand{\subsection}{\@startsection{subsection}{2}{0mm}%
                                     {1ex plus -1ex minus -.2ex}%
                                     {1ex plus .2ex}%
                                     {\normalfont\large\bfseries}}%
 \renewcommand{\subsubsection}{\@startsection{subsubsection}{3}{0mm}%
                                     {1ex plus -1ex minus -.2ex}%
                                     {1ex plus .2ex}%
                                     {\normalfont\normalsize\bfseries}}
 \renewcommand\paragraph{\@startsection{paragraph}{4}{0mm}%
                                    {1ex \@plus1ex \@minus.2ex}%
                                    {-1em}%
                                    {\normalfont\normalsize\bfseries}}
 \renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
                                       {2.0ex \@plus1ex \@minus .2ex}%
                                       {-1em}%
                                      {\normalfont\normalsize\bfseries}}
\makeatother

\newcounter{thelecture}

\newenvironment{proof}{{\bf Proof:  }}{\hfill\rule{2mm}{2mm}}
\newenvironment{proofof}[1]{{\bf Proof of #1:  }}{\hfill\rule{2mm}{2mm}}
\newenvironment{proofofnobox}[1]{{\bf#1:  }}{}
\newenvironment{example}{{\bf Example:  }}{\hfill\rule{2mm}{2mm}}

%\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\renewcommand{\thefigure}{\thesection.\arabic{figure}}

\newtheorem{fact}{Fact}
\newtheorem{lemma}[fact]{Lemma}
\newtheorem{theorem}[fact]{Theorem}
\newtheorem{definition}[fact]{Definition}
\newtheorem{corollary}[fact]{Corollary}
\newtheorem{proposition}[fact]{Proposition}
\newtheorem{claim}[fact]{Claim}
\newtheorem{exercise}[fact]{Exercise}

% math notation
\newcommand{\R}{\ensuremath{\mathbb R}}
\newcommand{\Z}{\ensuremath{\mathbb Z}}
\newcommand{\N}{\ensuremath{\mathbb N}}
\newcommand{\B}{\ensuremath{\mathbb B}}
\newcommand{\F}{\ensuremath{\mathcal F}}
\newcommand{\SymGrp}{\ensuremath{\mathfrak S}}
\newcommand{\prob}[1]{\ensuremath{\text{{\bf Pr}$\left[#1\right]$}}}
\newcommand{\expct}[1]{\ensuremath{\text{{\bf E}$\left[#1\right]$}}}
\newcommand{\size}[1]{\ensuremath{\left|#1\right|}}
\newcommand{\ceil}[1]{\ensuremath{\left\lceil#1\right\rceil}}
\newcommand{\floor}[1]{\ensuremath{\left\lfloor#1\right\rfloor}}
\newcommand{\ang}[1]{\ensuremath{\langle{#1}\rangle}}
\newcommand{\poly}{\operatorname{poly}}
\newcommand{\polylog}{\operatorname{polylog}}

% anupam's abbreviations
\newcommand{\e}{\epsilon}
\newcommand{\eps}{\epsilon}
\newcommand{\half}{\ensuremath{\frac{1}{2}}}
\newcommand{\junk}[1]{}
\newcommand{\sse}{\subseteq}
\newcommand{\union}{\cup}
\newcommand{\meet}{\wedge}
\newcommand{\dist}[1]{\|{#1}\|_{\text{dist}}}
\newcommand{\hooklongrightarrow}{\lhook\joinrel\longrightarrow}
\newcommand{\embeds}[1]{\;\lhook\joinrel\xrightarrow{#1}\;}
\newcommand{\mnote}[1]{\normalmarginpar \marginpar{\tiny #1}}

\newcommand{\OPT}{\textsf{OPT}}
\newcommand{\That}{\widehat{T}}
\newcommand{\Ghat}{\widehat{G}}
\newcommand{\chat}{\widehat{c}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Document begins here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\hwheadings}[3]{
{\bf Approximation Algorithms} \hfill {{\bf Homework #1}}\\
{{\bf Date:} #2} \hfill {{\bf Due:} #3} \\
\rule[0.1in]{\textwidth}{0.025in}
%\thispagestyle{empty}
}

\begin{document}

\hwheadings{5}{Nov 2, 2005}{Nov 9, 2005}

\textbf{Note:} In all these problems: if we ask you to show an
approximation ratio of $\rho$, you should tell us about the best
approximation ratio you did prove, be it better or worse than $\rho$.
Also, please refrain from consulting any external sources (papers,
lecture notes, books, surveys) in attempting to solve these problems.

\begin{enumerate}

\item Write an ILP formulation for the following problems. Try to be
as succinct as possible, i.e., use as few variables and constraints
as you possibly can. Write out in $O(\cdot)$-notation, the number of
variables and constraints in your solutions (E.g., the formulation
for Vertex Cover we saw in class had $O(|V|)$ variables and $O(|E| +
|V|)$ constraints in a graph $G= (V,E)$.

\begin{itemize}

\item {\bf Maximum s-t flow:} Given an undirected graph $G = (V, E)$
with a source node $s$ and sink node $t$, and nonnegative capacities
$c: E \to \R_+$ on the edges, find a "flow" of maximum value from
$s$ to $t$. Informally, an $s-t$ flow is a collection of paths from
$s$ to $t$ such that the number of paths using any edge $e$ is at
most the edge's capacity. Formally, a flow is a function that emits
a value at the source $s$ and absorbs it at $t$ while keeping it
conserved at all other nodes (think of Kirchoff's law for
electricity).

\item {\bf Minimum s-t cut:} Given an undirected graph $G = (V, E)$
with a source node $s$ and sink node $t$, and nonnegative capacities
$c: E \to \R_+$ on the edges, find a "cut" of minimum total edge
capacity separating $s$ and $t$. A cut is a subset of edges whose
deletion disconnects $s$ from $t$. Without loss of generality, it
can be defined by a subset $S \subset V$ of the nodes containing $s$
(i.e., $s \in S$) where the cut is the set of edges with exactly one
endpoint in $S$.

\item {\bf Minimum s-t path:} Given an undirected graph $G = (V, E)$
with a source node $s$ and sink node $t$, and nonnegative distances
$d: E \to \R_+$ on the edges, find a path of minimum total distance
connecting $s$ and $t$.

\end{itemize}

\item Recall the K-median problem we defined earlier; we give a
definition for the non-metric version here. Given an unweighted
graph $G = (V, E)$ with nonnegative (nonmetric) distances $d: E \to
\R_+$ and a number $K$, find a set $C$ of size $K$ that minimizes
$\sum_{v \in V} \min_{c \in C} d(x,c)$.

\begin{itemize}
  
\item Formulate the K-median problem as an ILP. Let the optimal value of
  its LP relaxation be $C$.

\item For the general (nonmetric) case, show how to round this LP
solution to an integer solution with at most $O((1 + \epsilon) \log
|V| \cdot K)$ medians of objective value $O((1 + \frac{1}{\epsilon})
\cdot C))$ for any $\epsilon > 0$. (Hint: Use the Filtering method
of Lin-Vitter from class to transform to a set covering problem.)

\item For the metric case (as in class, when distances obey the triangle
  inequality), show how to round this LP solution to an integer solution
  with at most $O((1 + \epsilon) \cdot K)$ medians of objective value
  $O((1 + \frac{1}{\epsilon}) \cdot C))$ for any $\epsilon > 0$.

\end{itemize}

\item In class, we saw an algorithm for the facility location problem
  that rounded the natural LP and obtained a $4$-approximation. Consider
  the following modified rounding procedure:
  \begin{itemize}
  \item \textbf{(Sampling Phase)} For each potential facility $i$,
    independently add it to a set $F_1$ with probability $y_i$. For a
    demand $j$, if some facility in $\{ i \mid x_{ij} > 0\}$ is picked
    in $F_0$, assign it to the closest such facility. Note that all
    demands may have not been assigned to facilities in this stage.


  \item \textbf{(Second Phase)} Use the filtering$+$clustering procedure
    from class to open more facilities, and assign the remaining demands
    to these facilities.
  \end{itemize}
  Argue that the expected cost of $F_0$ plus the expected cost of the
  assigned demands is not much larger than $Z_{LP}$. Now since the
  second phase is performed only on a smaller set of nodes, can you show
  that the expected cost of the entire procedure is better than $4
  Z_{LP}$?

\item We saw the $1|r_j|\sum_j C_j$ problem in class, and argued that
  given a preemptive schedule for the problem (with completion times
  $C_j^P$), we could change it into a non-preemptive schedule with
  completion times $C_j^N \leq 2C_j^P$.
  
  Now suppose you are given $m$ parallel identical machines (i.e., the
  problem called $P|r_j| \sum_j C_j$), and you have a preemptive
  schedule for this problem. (Note that a preemptive schedule for
  parallel machines must still ensure that any job can run on at most
  one machine at any given point in time; however, it can be stopped and
  continued later on \emph{any} machine.)
  
  Given a preemptive schedule for $m$ parallel identical machines, how
  do you into a non-preemptive schedule with completion times $C_j^N
  \leq 3C_j^P$?

  This immediately implies that $\sum_j C_j^N \leq 3 \sum_j C_j^P$, and
  hence a 3-approximation.

  \medskip\textbf{Note:} In the single machine case with release dates,
  the best preemptive schedule is given by SRPT. This is not the case
  with parallel machines, where the problem is NP-hard even on two
  machines.
\end{enumerate}

\end{document}