<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}



%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS~38~~~Introduction to Algorithms
                        \hfill Spring 2014} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Problem Set #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
      \vspace{2mm}}
   }
   \end{center}
   \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
            \vspace{0.2 in}
            \setlength{\epsfxsize}{#2}
            \centerline{\epsfbox{#4}}
            \begin{center}
            Figure \thelecnum.#1:~#3
            \end{center}
    }

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&amp;$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM
% HERE:


\newcommand{\set}[1]{\left \{{#1} \right \}}

\begin{document}
\problemset{7}{May 27}{\bf June 3}

Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the optional text (CLRS). The full honor code guidelines can be found in the course syllabus.


Please attempt all problems. {\bf To facilitate grading, please
turn in each problem on a separate sheet of paper and put your
name on each sheet. Do not staple the separate sheets.}
\begin{enumerate}
\item We are given subsets $S_1, S_2, \ldots, S_n$ of an $m$-element universe
  $U$. Recall that a cover is set $I$ such that
\[\bigcup_{i \in I}S_i = U.\]
In lecture 18, we saw a $(\ln m + 1)$-approximation algorithm for this
problem. In this problem you are asked to give a $k$-approximation algorithm for {\sc set
  cover} in the special case that no element $u \in U$ appears in more
than $k$ subsets. Hint: solve an LP relaxation, and round.

\item In the {\sc max cut} problem, we are given an undirected graph
  $G = (V,E)$ and we seek a {\em cut} with the maximum
  number of edges crossing it. An edge $(u,v)$ crosses a cut $S
  \subseteq V$ iff one of $u,v$ is in $S$ and the other is not in
  $S$. This problem is NP-complete. Formulate an LP relaxation and
  rounding scheme that yields a 2-approximation algorithm for this
  problem. Hint: your LP should have variables for each vertex and for
  each edge.

\item Faster maximum matching in a general graph. We saw in lecture 12 how to find a
  maximum bipartite matching in time $O(mn^{1/2})$ time, and we
  asserted that a more complex algorithm achieved a similar time bound
  for general graphs. In this problem you will show that if one is
  satisfied with a 2-approximation, then an $O(m)$ running time can be
  achieved by a very simple algorithm.
\begin{enumerate}
\item A {\em maximal} matching is a matching that cannot be enlarged
  by adding any edge. Show that one can find a maximal matching in
  $O(m)$ time in a general undirected graph.

\item Prove that every maximal matching has cardinality at least
  one-half of the cardinality of a maximum matching. Hint: relate
  both quantities to the cardinality of a minimum vertex cover.
\end{enumerate}

\item Bin packing. We are given a list of real numbers $a_1, a_2,
  \ldots, a_n$ and we wish to {\em pack} them into as few
  unit-capacity bins as possible. A unit-capacity bin can accommodate
  any subset of the $a$'s whose sum is at most $1$. This problem is
  NP-hard (it is even NP-complete to determine if 2 bins suffice).

  A simple strategy is to place each $a_i$ in turn into the first bin
  into which it can fit. Prove that this strategy is a 2-approximation
  algorithm for bin-packing.


\end{enumerate}
\end{document} </pre></body></html>