\documentclass[12pt]{article}
\newcommand{\Solution}{\textbf{SOLUTION:\ }}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\newcommand{\myspan}{\mbox{span}}

\usepackage{geometry}

\begin{document}
	\begin{center}
	\bf
	Advanced Topics in Algorithms \\
	Computer Science 181b\\
	Spring 2012\\
	\rm
	Homework 3, Due  Wednesday, February 8  \\
\end{center}

\begin{enumerate}

\item \textbf{[15 Points] Rank and Span Envy!}
	\begin{enumerate}
 		 \item 
	       Let $M=(E, \cal{I})$ be a matroid.  Analogous to the definition in a vector space, the 
            \emph{rank} of a set $X \subseteq E$, denoted $r(X)$, is the size of a largest independent
            subset of $X$.  Let $B$ be a basis of $M$.  Show that $r(B) = r(E) = |B|$.  (Remember, a set is a subset of itself.)

            
 		 \item 
  	   Recall that if $V$ is a vector space and $X \subseteq V$, the \emph{span}
  	   of $X$, denoted $\myspan(X)$, is defined to be the subspace of all vectors that can be
	   expressed as a linear combination of vectors in $X$.   It is easy to verify that in a vector space, $\myspan(X)$ is the unique maximal superset of $X$ with the same rank as $X$.
	   
	   If $M = (E, \cal{I})$ is a matroid and $X \subseteq E$, the span of $X$, denoted 
	   $\myspan(X)$, is defined to be any maximal superset $Y$ of $X$ such that $r(Y) = r(X)$.  (Remember, a set is a superset of itself.)
	   
	    \begin{enumerate}
	   		\item In a vector space, each subset of vectors has a unique span.  Is this true for matroids?  If so, prove it.
	   If not, give a small counterexample.

									
	   		\item Another property of vector spaces is that for
	   any basis $B$ in a vector space $E$, $\myspan(B)$ is the entire vector space.  Is the corresponding property, that 
	   $\myspan(B) = E$ for any basis $B$, true in all matroids?  If so, prove it.  If not, demonstrate a small counterexample.
	   
	   \end{enumerate}	   
	  \end{enumerate}
   
\item \Points{35} \Name{The Millisoft Matching Problem!}
	In this problem we investigate a graph matching problem and its corresponding
	matroid.

	Gill Bates, CEO of Millisoft,  has come up with a revolutionary new scheme for matching 
	up pen pals.   He plans to offer the service through his MilliSoft Network web site in the near future.

	Assume that there are $n$ subscribers to the service.  Ideally, every  subscriber in the network will be paired up with exactly one other subscriber.  For compatibility reasons, only certain pairs of 
	subscribers can be matched and it therefore may not be possible to find a match for every subscriber.
	Each subscriber stipulates a single positive fee that they are willing to pay to get matched. 
	Millisoft would like to find a matching that maximizes the total fees
	that it can collect from the subscribers.

	This optimization problem can be represented with a general graph in which vertices
	correspond to subscribers, edges correspond to subscribers that can
	potentially be matched, and the weight on each vertex represents the fee
	that will be paid if that vertex is matched.   Our objective is to find a
	matching that maximizes the sum of the weights on the matched vertices. 
	
	\begin{enumerate}
		\item Explain why this problem is more general than the matching problem in unweighted general graphs but is less general than the matching problem in weighted general graphs.  (That is, show that it contains the former problem as a special case and is also a special case of the latter problem.)
		

		
		\item Show that this problem can be solved using the Matroid Greedy Algorithm.  Let $M=(E, I)$ be defined as follows:  $E$ is the set of all vertices of the graph and $X \subseteq E$ is in $I$ if there exists some matching in which all of the vertices of $X$ are matched (possibly to vertices of $E-X$).  Show that this is a matroid and that our problem is that of finding a basis of maximum weight in this matroid.   
		
		
		\item Since the problem can be formulated as finding a basis of maximum weight in this matroid, we can apply the Matroid Greedy Algorithm (MGA) to solve the problem.  The MGA requires that we test sets for
		independence.  Explain how the independence test would work in this context.  Rather than devising a special algorithm for the independence test (which would potentially require a challenging proof of correctness), show
		how the independence test can be performed by constructing an appropriate graph and applying a known correct  algorithm on this graph.  You'll still need to prove that your method is correct, but
		the argument will be much nicer because you'll be using the correctness of an ``off-the-shelf'' algorithm.
		
		
		\item What is the running time of your algorithm?  Explain. (It needn't be the fastest possible, just polynomial time.)

	\end{enumerate}

	

\item \Points{15} \Name{Chromatic Spanning Trees.}
The Republic of Shmorbodia is planning to build a new spanning network to span all of its government buildings.  Shmorbodia has $k$ different private internet provides, each of which owns some set of the cables.  Thus, you can imagine that each edge has a weight (cost) and a color, where the color indicates the provider that owns that cable.  (The graph is simple; it is not a multigraph.)  In the spirit of fairness, the Republic has set a limit $m_i$ on the number of cables that can be rented from each provider $i$, $1 \leq i \leq k$.  The objective is to find the spanning tree of minimum weight subject to the constraint on the number of cables rented from each provider.  Explain how this problem can be solved using an algorithm mentioned in class or solved in another homework problem.


\item \Points{35} \Name{The Matroid Intersection Theorem.}
The Matroid Intersection Theorem states that for any two matroids over the same ground set $E$, $M_1 = (E, I_1)$ and $M_2 = (E, I_2)$ with rank functions $r_1$ and $r_2$, respectively:
\[
max_{X \in I_1 \cap I_2} |X| = min_{U \subseteq E} (r_1(U) + r_2(E-U))
\]
	\begin{enumerate}
		\item Use this theorem to prove K\"{o}nig's Matching Theorem that states that in a bipartite graph, the size of a maximum matching is equal to the size of a minimum vertex cover.  (That's our third \emph{different} proof of this result!)
		
		
		\item Use the Matroid Intersection Theorem to prove `` K\"{o}nig's Other Theorem'' (aka the  K\"{o}nig-Rado Theorem) that states that in a bipartite graph, the size of a minimum edge cover is equal to the size of a maximum independent set.  Recall that an edge cover is a set of edges that cover all the vertices in the graph.  (\emph{Hint:}  Use the same matroids as for part (a).  It may useful to first show that the complement of a vertex cover is an independent set -- a set of vertices no two of which are connected to one another -- and thus minimizing the size of a vertex cover is equivalent to maximizing the size of an independent set.)
		
	       		
	\end{enumerate}

\end{enumerate}
\end{document}

  \item \Points{30} \Name{The Dynamic List Access Problem!}
 In class we looked at the MTF online algorithm for the List Access
Problem.  Specifically, we looked at the \textbf{Static} List Access
Problem where only \textsc{Find}s were allowed - there were no \textsc{Insert} and \textsc{Delete}
operations permitted in the request sequence.

Now, consider the more general \textbf{Dynamic} List Access Problem which
differs from the static version in three ways:
  \begin{enumerate}
    \item Any \textsc{Find} operation may fail.  That is, the item might not be
found.  In this case, the actual cost is $\ell + 1$ where $\ell$ was the
length of the list at the time that the \textsc{Find} was performed. 

    \item \textsc{Insert} operations are permitted in the request sequence.  An
inserted object is placed at the end of the list.  If the length of the
list prior to the \textsc{Insert} was $\ell$, then the actual cost of this
operation is $\ell + 1$.  After inserting the element at cost $\ell + 1$,
you may move it to any position earlier in the list at no cost (just like
in a successful \textsc{Find} operation).

   \item \textsc{Delete} operations are permitted in the request sequence.  The
cost of the \textsc{Delete} is simply the cost of finding the object.  (However,
the potential function changes as a consequence of the \textsc{Delete}, so a
\textsc{Delete} differs from a \textsc{Find} in this way!)
  \end{enumerate}

Describe a modification of the MTF algorithm to handle all three of these operations.
Show that when your modified MTF algorithm is applied to the Dynamic List Access Problem, it
still maintains a competitive ratio of 2.  (That is, it is 2-competitive
with respect to an optimal offline algorithm.)



\end{document}

