\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSG399}{Approximation Algorithms}{Spring 2004}{25 February 2003}{5}

\begin{center}
\Large{\bf Problem Set 3 (discussion day: March 8)}
\end{center}

\bigskip

\newcommand{\partition}{{\sc Partition}}

{\bf 1.} {\bf PARTITION}

Consider the following optimization version of the \partition\ 
problem.  Given a set $X = \{x_1, x_2, \ldots, x_n\}$ of $n$ integers,
find a partition of $X$ into two subsets $X_1$ and $X_2$ that
minimizes the quantity:
\[\max\{ \sum_{x \in X_1} x, \sum_{x \in X_2} x \}.\]

In this exercise, we derive a PTAS for the \partition\ problem using
the enumeration technique we used to dervive PTASs for knapsack and
bin-packing.

Consider the following heuristic for some fixed integer $k$: (i)
Choose the $k$ largest $x_i$'s.  (ii) Find the optimal partition of
these $k$ integers using some exhaustive method.  (iii) Complete this
into a partition of $X$ by considering each of the remaining $x_i$'s
in turn and adding it to the partition which at the time has the
smallest sum.
\begin{itemize}
\item[{\bf (a)}] {\bf (3 points)} Show how to implement the above heuristic
  in time $O(2^k + n)$.
  
\item[{\bf (b)}] {\bf (12 points)}  Prove that the above heuristic achieves
  an approximation ratio of $1 + \frac{1}{2 + k}$.
  
\item[{\bf (c)}] {\bf (5 points)} Using the claims of parts~(a)
  and~(b), choose $k$ appropriately such that the above heuristic
  yields a PTAS for \partition.
\end{itemize}

\newcommand{\is}{{\sc IndependentSet}}
{\bf 2.} An {\em independent set}\/ of an undirected graph
$G$ is a subset $V'$ of vertices such that no two vertices in $V'$
have an edge in $G$.  The \is\ problem is to find a maximum-size
independent set in $G$.  It is known that \is\ is NP-complete.  In
this problem, we investigate the approximability of \is.

Define the {\em product}\/ of two graphs $G_1 = (V_1, E_1)$ and $G_2 =
(V_2, E_2)$ as $G = (V, E)$, where
\[V = \{\langle
v_1, v_2 \rangle: v_1 \in V_1, v_2 \in V_2\},
\] 
and there is an edge between vertices $\langle u_1, u_2 \rangle$ and
$\langle v_1, v_2 \rangle$ in $G$ if either $u_1 = v_1$ and $(u_2,
v_2) \in E_2$ or $(u_1, v_1) \in E_1$.  For a positive integer $n$,
let $G^n$ be defined by the recurrence relation $G^{i+1} = G^i \times
G$ and $G^1 = G$.
\begin{itemize}
\item[{\bf (a)}] {\bf (5 points)} Prove that $G$ has an independent set of size $k$ if
  and only if $G^n$ has an independent set of size $k^n$.
  
\item[{\bf (b)}] {\bf (5 points)} Give a polynomial-time algorithm to
  construct an independent set of $G$ of size $\lceil k^{1/n} \rceil$
  from any independent set of $G^n$ of size $k$.
  
\item[{\bf (c)}] {\bf (10 points)} Using parts~(a) and~(b), argue that
  if there exists a constant $c$ such that there is a polynomial-time
  $c$-approximation algorithm for \is, then there exists a PTAS for
  \is.
\end{itemize}

{\bf 3.} The {\em bottleneck TSP problem} is the problem of finding a
Hamiltonian cycle in a given weighted undirected graph such that the
length of the longest edge in the cycle is minimized.  Assuming that
the input graph satisfies the triangle inequality, show that this
problem has a polynomial-time approximation algorithm with ratio $3$.

{\bf 4.} Exercise 3.10.

{\bf 5.} Exercise 11.3.

\end{document}

