\documentclass[12pt]{article}
\usepackage{fullpage}
%\usepackage{times}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\newcommand{\myparskip}{6pt}
\parskip \myparskip
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{assumption}[lemma]{Assumption}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{prop}[lemma]{Proposition}
\newtheorem{claim}[lemma]{Claim}
\newtheorem{remark}[lemma]{Remark}
\newtheorem{prob}{Problem}
\newenvironment{myprob}{\begin{prob} \em}{\end{prob}}
\newcommand{\opt}{\mbox{\sc opt}}
\newcommand{\eps}{\epsilon}
\begin{document}
\setlength{\fboxrule}{.5mm}\setlength{\fboxsep}{1.2mm}
\newlength{\boxlength}\setlength{\boxlength}{\textwidth}
\addtolength{\boxlength}{-4mm}
%\begin{center}\framebox{\parbox{\boxlength}{%\bf
\begin{center}
{\bf Fall 2013, CS 583: Approximation Algorithms\\~\\
Homework 0}\\
Due: 09/06/2013 in class
\end{center}
%}}\end{center}
\vspace{5mm}
\noindent {\bf Collaboration Policy:} This homework is to test your
knowledge of pre-requisite material and will not be officially graded. Try to
work out the problems on your own but feel free to talk to other
students.
\noindent {\bf What to turn in:} Solutions to two or more problems. We want to get a sense of how you write formally and
whether you have sufficient background.
%I expect you to think about these problems since
%future homeworks might make use of some of the observations.
%You must do problems $1$ to $5$ {\em on your own} without referring to
%texts/papers. Collaboration on $6$ is allowed.
%\noindent
%Problems to test knowledge of algorithms.
\iffalse
\begin{myprob} We are given a set of $n$ intervals on the real line,
$I_1, I_2, \ldots, I_n$. Each interval $I_j$ is specified as
$(\ell_i, r_i)$ where $\ell_i$ is the left end point and $r_i$ is the
right end point. There is a positive weight $w_j$ associated with
$I_j$. Use dynamic programming to find the maximum weight subset of
intervals that do not overlap. Suppose we allow intervals to overlap but we
require that the maximum number of intervals that can contain
any point $x$ on the real line is $B$ for some constant $B > 1$.
Can you generalize your algorithm to find a maximum weight subset
of intervals that satisfy this relaxed condition? What is the running
time of your algorithm?
\end{myprob}
\fi
\begin{myprob}
Lipton and Tarjan showed that for any $n$ vertex planar graph
there is a balanced separator of size at most $C\sqrt{n}$ for
some absolute constant $C$ that does not depend on $n$ or the graph.
A balanced separator is a set of vertices whose removal partitions
the graph into two disconnected graphs each with no more than
$2n/3$ vertices. They also show that such a separator can be
found in polynomial time. Use these facts to show how to compute
a maximum independent set in $G$ in $2^{O(\sqrt{n})}$ time.
An independent set in a graph is a set of vertices with no
edge between any two vertices in the set (also called a stable
set).\\
{\bf Hint:} Use divide and conquer and dynamic programming.
\end{myprob}
\begin{myprob}
Ball and bins. Consider throwing $n$ balls into $n$ bins where each
ball is thrown independently and uniformly at random into a bin. What
is the probability that a given bin (say the first bin) is empty?
What is the probability that it contains exactly $k$ balls? What is
the expected number of bins that are empty?
If you know Chernoff bounds prove that the
maximum number of balls in any bin is $O(\log n/\log \log n)$
with high probability (with probability at least $1 - 1/\text{poly(n)}$).
If you do not know Chernoff bounds, using more elementary methods,
show a weaker bound of $O(\log n)$.
\iffalse
Argue
that it contains no more than $c \log n/\log \log n$
balls with high probability: that is with probability
at least $1 - 1/n^\alpha$ for some $\alpha > 1$ if
$c$ is a sufficiently large constant. Using this
prove that all bins have $O(\log n/\log \log n)$
balls with high probability. It is slightly harder
to prove that the the maximum
occupancy is $\Theta(\log n/\log \log n)$. See
if you can prove this.
\fi
\end{myprob}
\begin{myprob}
The classical $0,1$ knapsack problem is the following. We are given
a set of $n$ items. Item $i$ has two positive integers associated
with it: a size $s_i$ and a profit $p_i$. We are also given a
knapsack of integer capacity $B$. The goal is to find a maximum
profit subset of items that can fit into the knapsack. (A set of
items fits into the knapsack if their total size is less than the
capacity $B$.) Use dynamic programming to obtain an exact algorithm
for this problem that runs in $O(nB)$ time. Also obtain an algorithm
with running time $O(nP)$ where $P = \sum_{i=1}^n p_i$. Note that
both these algorithms are not polynomial time algorithms. Do you see
why?
\iffalse
Now we consider a greedy algorithm for this problem. Assume without
loss of generality that the items are numbered such that $s_1/p_1 \le
s_2/p_2 \le \ldots \le s_n/p_n$. The algorithm considers items in this
order and places them in the knapsack until for the first time an item
cannot be placed because it would violate the knapsack capacity.
Let $p_G$ be the profit of items packed by Greedy when it stops.
Suppose for some $\eps < 1$, $s_j \le \eps B$ for $1\le j \le n$.
Show that $p_G \ge (1-\eps)O$ where $O$ is the
value of an optimum solution.
\fi
\end{myprob}
\begin{myprob}
In the (maximum-cardinality) matching problem, given a graph
$G(V,E)$, the goal is to find a largest subset of edges $E'$ such
that no two edges in $E'$ share a common vertex. (Equivalently, each
vertex must be adjacent to at most one edge in $E'$.)
\begin{enumerate}
\item Write a Linear Program (LP) for the matching problem in
bipartite graphs.
\item Write a linear program for the matching problem in general graphs.
\item Write the duals to the primal linear programs from parts 1
and 2.
\item Give an example to show that there is a fractional solution
to the LP of part 2 with value greater than that of an optimal
integral solution. (That is, the \emph{integrality gap} of this
linear program is greater than 1.)
\item Prove that the optimal value to the LP of part 1 is an
integer.\\
{\bf Hint:} You may use the fact that the in a network
with integer capacities, the value of the maximum flow is
integral.
\end{enumerate}
\end{myprob}
\begin{myprob}
Let $G$ be a complete graph with non-negative edge weights. One can
compute in polynomial time a minimum weight perfect matching in $G$
(assuming $G$ has an even number of vertices). We want to use the
matching algorithm to solve a problem on directed graphs. Let
$H=(V,E)$ be a {\em directed} graph with non-negative arc weights
given by $w:E \rightarrow {\cal R}^+$. We wish to find a minimum
weight collection of vertex-disjoint directed cycles in $H$ such that every
vertex is in exactly one of those cycles. Show that one can solve
this problem by reducing it to the matching problem.\\
{\bf Hint:} Split each vertex $v$ in $H$ into two vertices $v^-$ and
$v^+$ with $v^-$ for incoming arcs into $v$ and $v^+$ for outgoing
arcs from $v$.
\end{myprob}
\end{document}