\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 1}\\
Due: 09/20/2013
\end{center}
%}}\end{center}
\vspace{5mm}
\noindent {\bf Instructions and Policy:} Each student should write up
their own solutions independently. You need to indicate the names of
the people you discussed a problem with; ideally you should discuss
with no more than two other people.
\noindent
Solve as many problems as you can. Please submit your
solutions to at least 4 problems.
\noindent
Please write clearly and concisely - clarity and brevity will be
rewarded. Refer to known facts as necessary. Your job is to convince
me that you know the solution, as quickly as possible.
\begin{myprob}
Consider the $k$-dimensional knapsack problem. We are given $n$
non-negative $k$-dimensional vectors $\bar{v}_1, \bar{v}_2,\ldots,
\bar{v}_n$. Each vector has a non-negative weight, $w_i$ for
$\bar{v}_i$. We are also given a $k$-dimensional knapsack $\bar{V}$
and the goal is to find a maximum weight subset of vectors that pack
in to $V$. A subset of vectors pack into $\bar{V}$ if their vector
addition is less than $\bar{V}$ (co-ordinate wise). Prove that there
is a pseudo-polynomial time algorithm for this problem when $k$ is a
fixed constant independent of $n$. What is the running time of your
algorithm? Prove that even for $k=2$ and {\em unit weights} the
problem does not admit an FPTAS. (Hint: use a reduction from the
Partition problem.) {\bf Extra credit:} Obtain a PTAS
for this problem when $k$ is a fixed constant independent of $n$
(might need to use LP techniques).
\end{myprob}
\begin{myprob}
Consider a budgeted version of the maximum coverage problem. We are
given $m$ sets $S_1, S_2, \ldots, S_m$, each a subset of a set $\cal
U$. Each set $S_i$ has a non-negative cost $c_i$ and we are also
given a budget $B$. The goal is to pick sets of total cost at most
$B$ so as to maximize the number of elements covered. Show that if
$c_i \le \epsilon B$ for $1\le i \le m$ then the Greedy algorithm
yields a $1-1/e - \epsilon$ approximation (for sufficiently small
$\epsilon$). For any fixed $\epsilon > 0$ obtain a $1-1/e -
\epsilon$ approximation. (Hint: consider the PTAS for knapsack from
the lectures. You might find the inequality $1-x \leq e^{-x}$
useful.) {\bf Extra credit:} Obtain a $1-1/e$ approximation for this
problem.
\end{myprob}
\begin{myprob}
In the submodular set cover problem, we are given a universe
$\cal{U}$ of elements, and a monotone submodular function $f \colon
2^{\cal{U}} \rightarrow \mathbb{\cal{R}}^+$. The goal is to pick a
smallest $U' \subseteq \cal{U}$ such that $f(U') = f(\cal{U})$. In
the submodular maximum coverage problem, we are also given an
integer $k$, and the goal is to pick a set $U' \subseteq \cal{U}$ of
size at most $k$ to maximize $f(U')$.
\begin{enumerate}
\item Prove that the greedy algorithm gives a $1 - 1/e$
approximation for submodular maximum coverage.
\item Consider a $k \times \ell$ matrix $M$ where each entry
$M_{i,j}$ is a subset of a universe $\cal{U}$ of size $n \ge
\ell$. We say a row $M_i$ of $M$ is \emph{covered} by $U'
\subseteq \cal{U}$ if there are $\ell$ {\em distinct} elements
$e_1, e_2, \ldots e_\ell$ in $U'$ such that $e_j \in M_{i,j}$
for each $1 \le j \le \ell$.
Prove that the problem of finding a smallest $U' \subseteq
\cal{U}$ such that each row is covered by $U'$ is a special case
of the submodular set cover problem.
\end{enumerate}
\end{myprob}
\begin{myprob}
Problem 3.6 from Shmoys-Williamson book.
\end{myprob}
\begin{myprob}
Problem 13.4 from Vazirani book.
\end{myprob}
\begin{myprob}
Problem 1.4 from Shmoys-Williamson book.
\end{myprob}
\end{document}