\documentclass[12pt]{article}

\usepackage{graphicx}
\usepackage{amsmath,amssymb,url}
\usepackage{bbm}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\parskip 1.5ex  \parindent 0ex \footskip 20pt

 
\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in}
{\bssdoz CME 305: Discrete Mathematics and Algorithms}
{\\ \bssten Instructor: Reza Zadeh (rezab@stanford.edu) }
{\\ \bssten HW\#4 --  Due at the beginning of class Thursday 03/16/17}
\vspace{5pt}

\begin{enumerate}


\item Let $G=(V,E)$ be a $c$-edge connected graph. In other words, assume that the size of minimum cut in $G$ is at least $c$. Construct a graph $G'(V, E')$ by sampling each edge of $G$ with probability $p$ independently at random and reweighing each edge with weight $1/p$. Suppose $c > \log n$, and $\epsilon$ is such that $ \frac{10\log(n)}{c \epsilon^2} \leq 1$. Show that as long as $p \geq \frac{10\log(n)}{c \epsilon^2}$, with high probability the size of every cut in $G'$ is within $(1\pm \epsilon)$ of the cut in the original graph $G$.


\item Let $V$ be a finite set.  A function $f\colon 2^V \to R$ is submodular iff for any $A,B \subseteq V$, we have
$$  f(A \cap B) + f(A \cup B) \leq f(A)+f(B)$$
Now consider a graph with nodes $V$. For any set of vertices $S\subseteq V$ let $f(S)$ denote the number of edges $e=(u,v)$ such that $u\in S$ and $v\in V-S$. Prove that $f$ is submodular.


\item A square integer matrix $A$ is {\bf unimodular} if and only if
  its determinant is $-1$ or $1$.  A matrix (not necessarily square)
  $M$ is {\bf totally unimodular} iff every square submatrix has
  determinant $1$, $-1$, or $0$, i.e. every non-singular square submatrix is
  unimodular.

  Show that for a linear program with totally unimodular 
  constraint matrix $M$ and integral right-hand side $c$, all extreme
  points must be integral.

\item Given a list of personnel ($n$ persons) and of list of $k$
  vacation periods, each period spanning several contiguous vacation
  days.  Let $D_j$ be the set of days included in the $j$th vacation
  period. You need to produce a schedule satisfying:
\begin{itemize}
\item For a given parameter $c$, each tech support person should be
  assigned to work at most $c$ vacation days total.
  \item For each vacation period $j$, each person should be assigned to work
  at most one of the days during the period. 
  \item Each vacation day should be assigned a single tech support person.
  \item For each person, only certain vacation periods are viable.
\end{itemize}
  Describe a polynomial time algorithm to generate an assignment or output
  that no assignment exists.  Prove correctness. 
  
 \item Let $G$ be a graph $n$ nodes and an independent set of size $2n/3$. Give a polynomial time algorithm to find an independent set of size $n/3$ or greater -- find a 1/2-approximation to the independent set in this graph.
  
  \item The \textit{directed} cut size is the number of \textit{outgoing} edges from a cut $S$. The directed MAX-CUT problem asks for
  the cut with maximum directed cut size. Give a $1/4$ approximation algorithm for this problem.
  
  
  \item  Online social networks carry a huge potential for online advertising.
After a recent controversy, a popular
social networking platform does not allow advertisers to target the
users individually. However, it is allowed to run ads on user
communities.

Formally, let $X$ be the set of all users on a social network, and
$S_1, S_2, \ldots, S_m$ be subsets of $X$, where each $S_i$
represents a user community. Notice that a user can belong to
several communities. Suppose the advertiser can afford placing ads
on at most $k$ communities. The goal is to show the ads to as many
users as possible, i.e.\ to find $S_{i_1}, S_{i_2}, \ldots, S_{i_k}$
such that $|\cup_{j=1}^{k} S_{i_j}|$ is maximized.

Unfortunately, this problem is NP-hard and therefore we are
interested in designing efficient approximation algorithms to solve
it. Consider the following greedy approach: pick the $k$ communities
one at a time, and in each iteration pick the community that
contains the largest number of users that have not been covered yet.
In other words, choose the community that maximizes the current
coverage. Show that this greedy approach yields at least $1 - (1 -
1/k)^k > 1 - 1/e$ fraction of the optimal solution.

Hint: Let $x_i$ denote the number of new elements covered by the
algorithm in the $i$-th set that it picks. Also, let
$y_i=\sum_{j=1}^i x_j,$ and $z_i = OPT - y_i$. Show $x_{i+1} \geq
z_i/k$ and prove by induction that $z_i \leq (1 - 1/k)^{i} OPT$.

\item The \emph{knapsack problem} is a very well studied NP-hard combinatorial optimization problem. Given $n$ items with (positive) weights $w_1,w_2,\dots,w_n$ and associated values $v_1,v_2\dots,v_n$ and a bag that can hold total weight $W$, determine the number of each items to feasibly place in the bag (total weight chosen at most $W$) to maximize the value of items chosen. Give an algorithm to solve this problem with running time $O(nW)$.

Note that in the above version we assume an unlimited supply of every item, but there are variants with limits on each item that can be solved in the same running time in a very similar manner. Finally, note that the above running time is not necessarily polynomial because $W$ is not necessarily polynomial in $n$.

\item The \emph{max weight independent set} problem is the following: given an undirected graph $G = (V,E)$ and a weight function on the vertices $w: V \rightarrow \mathbb{R}$, output the independent set of $G$ with the maximum weight, where we define the weight of the set $S$ as $\sum_{v\in S} w(v)$. Our usual notion of maximum independent set problem is just a special case of this problem with all weights equal to 1, so this problem is also NP-hard.

However, we can solve it on trees (in fact, if you're interested, we can solve this problem on graphs with bounded treewidth). Give a polynomial time algorithm to solve this problem on trees.

\end{enumerate}

\end{document}
