% -*- compile-command: "rubber -d hw.10.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage{times,graphicx,epstopdf,fancyhdr,amsfonts,amsthm,amsmath,url,xspace}
\usepackage[linesnumbered,ruled]{algorithm2e}
% \usepackage[left=.75in,top=.75in,right=.75in,bottom=.75in]{geometry}

\usepackage{qrcode, enumitem}

\pagestyle{fancy}

\newcommand{\ie}{\emph{i.e.}\xspace}
\newcommand{\term}[1]{\emph{#1}}

\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}

\theoremstyle{definition}
\newtheorem{question}{Question}

\begin{document}

\lhead{CSCI 280: Algorithms -- Spring 2016}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 10}
\cfoot{\thepage}
\rfoot{Due: 4:00pm, Friday, April 22}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

\begin{question}[K\&T 8.4]
  Suppose you're consulting for a group that manages a
  high-performance real-time system in which asynchronous processes
  make use of shared resources.  Thus the system has a set of $n$
  \emph{processes} and a set of $m$ \emph{resources}.  At any given
  point in time, each process specifies a set of resources that it
  requests to use.  Each resource might be requested by many processes
  at once; but it can only be used by a single process at a time.
  Your job is to allocate resources to processes that request them.
  If a process is allocated all the resources it requests, then it is
  \emph{active}; otherwise it is \term{blocked}. You want to perform
  the allocation so that as many processes as possible are active.  Thus
  we phrase the \textsc{Resource Reservation} problem as follows:
  Given a set of processes and resources, the set of requested
  resources for each process, and a number $k$, is it possible to
  allocate resources to processes so that at least $k$ processes will
  be active?

  Consider the following list of problems.  For each problem either
  give a polynomial-time algorithm or prove that the problem is
  NP-complete.

  \begin{itemize}
  \item The general \textsc{Resource Reservation} problem defined
    above.
  \item The special case of the problem when $k = 2$.
  \item The special case of the problem when there are two types of
    resources---say, people and equipment---and each process requires
    at most one resource of each type. (In other words, each process
    requires at most one specific person and one specific piece of
    equipment.)
  \item The special case of the problem when each resource is
    requested by at most two processes.
  \end{itemize}
\end{question}

\begin{question}[K\&T 8.5]
  Consider a set $A = \{a_1, \dots, a_n\}$ and a collection $B_1,
  B_2, \dots, B_m$ of subsets of $A$ (\ie, $B_i \subseteq A$ for
  each $i$).

  We say that a set $H \subseteq A$ is a \term{hitting set} for the
  collection $B_1, B_2, \dots, B_m$ if $H$ contains at least one
  element from each $B_i$---that is, if $H \cap B_i$ is not empty for
  each $i$ (so $H$ ``hits'' all the sets $B_i$).

  We now define the \textsc{Hitting Set} problem as follows.  We are
  given a set $A = \{a_1, \dots, a_n\}$, a collection
  $B_1, B_2, \dots, B_m$ of subsets of $A$, and a number $k$.  We are
  asked: Is there a hitting set $H \subseteq A$ for
  $B_1, B_2, \dots, B_m$ whose size is at most $k$?

  Prove that \textsc{Hitting Set} is NP-complete.
\end{question}

\begin{question}[K\&T 8.6] Consider an instance of the
  \textsc{Satisfiability} problem, specified by clauses $C_1, \dots,
  C_k$ over a set of Boolean variables $x_1, \dots, x_n$.  We say that
  the instance is \term{monotone} if each term in each clause consists
  of a nonnegated variable; that is, each term is equal to $x_i$, for
  some $i$, rather than $\overline{x_i}$.  Monotone instances of
  \textsc{Satisfiability} are very easy to solve: they are always
  satisfiable, by setting each variable equal to $1$.

  For example, suppose we have the three clauses \[ (x_1 \lor x_2),
  (x_1 \lor x_3), (x_2 \lor x_3). \]  This is monotone, and indeed the
  assignment that sets all three variables to $1$ satisfies all the
  clauses.  But we can observe that this is not the only satisfying
  assignment: we could also have set $x_1$ and $x_2$ to $1$, and $x_3$
  to $0$.  Indeed, for any monotone instance, it is natural to ask how \emph{few}
  variables we must set to $1$ in order to satisfy it.

  Given a monotone instance of \textsc{Satisfiability}, together with
  a number $k$, the \emph{Monotone Satisfiability with Few True
    Variables} problem asks: is there a satisfying assignment for the
  instance in which at most $k$ variables are set to $1$?  Prove that
  this problem is NP-complete.
\end{question}

\end{document}
