\documentclass[12pt]{article}
\usepackage{graphics,epsfig}

\usepackage{fullpage}
\begin{document}

\begin{center}
\textbf{CS 141} \\ Advanced Topics in Algorithms \\ Spring 2004 \\
Problem Set 6b \\ Due Monday, March 1
\end{center}

\begin{enumerate}

  \item \textbf{[10 Points] Just Review.}
	Recall that the  \emph{Matroid Theorem} states the following:  ``The Matroid Greedy Algorithm
	returns a basis of maximum weight.''  Write down the proof of this theorem in your own words.  Be
	precise and rigorous.  
	
  \item \textbf{[40 Points] The Millisoft Matching Problem!}
In this problem we
investigate another discrete optimization problem and its corresponding
matroid.

Gill Bates 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 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 modelled as a 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.  Recall that a
\emph{matching} in a graph is defined to be a set of edges of $G$ such
that no two edges share a common vertex. Our objective is to find a
matching that maximizes the sum of the weights on the matched vertices.

Notice that this graph matching problem is slightly different from the one
that arose in the task assignment problem.  First, the graph that models
this problem is not necessarily bipartite.  In addition, in this problem
every vertex has an associated weight.

To solve this problem we consider a new matroid called a
\emph{matching matroid}.
Let $G=(V,E)$ be a graph.  Define $X \subseteq V$ to be \emph{matchable}
if there exists some matching $M \subseteq E$  such that every vertex
in
$X$ is incident on some edge in $M$. 
For convenience, we say that an edge in $M$ \emph{covers} its endpoints or
$M$ covers the set $X$.
Unlike the case of the bipartite matchings in the task assignment
problem, an edge in matching $M$ may be incident on zero, one, or two
vertices in $X$.  
Let $\mathcal{I}$ be the set of all matchable subsets of $V$.  
Assume that we already have an algorithm that determines whether or not a
set is matchable and, if it is matchable, the algorithm constructs a
matching for it.

	 \begin{enumerate}
    \item If $M_M = (V, \mathcal{I})$ is a matroid and $w$ is a weight
function from the vertices to the positive reals, show that a basis of
maximum weight in $M_M$ corresponds to an optimal solution to this
optimization problem.


		  \item  We will now show that $M_M$ is a
matroid in a sequence of steps.  Begin by showing that $M_M$ satisfies the
heredity property.

				\item To show that the exchange property is satisfied, begin by 
		  considering $X, Y \in \mathcal{I}$ such that $|X| > |Y|$ and consider
	   matchings $M_X$ and $M_Y$ that cover $X$ and $Y$, respectively. 
    Argue that if $M_Y$ covers a vertex in $X-Y$ then the exchange
    property is satisfied.    

		  \item Now consider the case that $M_Y$ covers no vertex in
    $X-Y$.  
    Color the edges in $M_X - M_Y$
    black, color the
	   edges in $M_Y - M_X$ white, and color the edges in $M_X \cap M_Y$
    gray.  
    Show that the gray edges cover at
    least as many vertices in $Y$ as in $X$.

    \item 
Recall that an \emph{alternating path} and an \emph{alternating cycle}
    is a path and cycle, respectively, that alternates
    between black and white edges.
    Show that the edges on the alternating cycles cover at
    least as many
    vertices in $Y$ as in $X$.

    \item Show that \emph{collectively} all the alternating paths contain more vertices of $X$
    than $Y$.  Note that this implies that some alternating path contains more vertices in $X$ than $Y$.

    \item Show that an endpoint of an alternating path cannot be in both
$X$ and $Y$.

    \item Show that there exists an alternating path $v_1, \dots, v_k$
such that $v_1 \in X-Y$ and $v_k \notin Y$.

    \item Show that $Y + v_1 \in \mathcal{I}$ by showing that a matching
exists that covers this set.  Conclude that $M_M$ is a matroid.
	 \end{enumerate}


\item \textbf{[10 Points] Try it Out!} As an example of the optimization
problem described in Problem~1, consider a network comprising five
subscribers, $a, b, c, d, e$, represented by the graph in the figure below.  An
edge between two vertices indicates that the corresponding subscribers are
compatible and may be matched to one another.  The number next to each
vertex represents the fee (or weight) associated with that subscriber. 
Use the Matroid Greedy Algorithm to find an optimal solution for this
instance of the optimization problem. Briefly explain what the Matroid
Greedy Algorithm selects at each iteration.  You will have to do the
matchability test by inspection.

    \begin{figure}[htbp]
     \begin{center}
  	\includegraphics[height=2in]{matroidfigure.pdf}
     \end{center}
    \end{figure}


	\end{enumerate}


\end{document}