\documentclass[11pt]{article}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}

\newcommand{\ABox}{
\raisebox{3pt}{\framebox[6pt]{\rule{6pt}{0pt}}}
}
\newenvironment{proof}{{\bf Proof:}}{\qquad\ABox}
%-------------------------------------------------
\newtheorem{observation}[theorem]{Observation}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}

\def\epf{ \hfill $\Box$ }
\def\myangle{\alpha}
\def\E{{\cal E}}
\def\S{{\cal S}}
\def\rs{\rho}
\def\dollars{\delta}
\def\fs{\phi}
\def\density{\mbox{density}}
\def\OPT{\mbox OPT}
\def\I{{\cal I}}
\def\R{{\mbox{``R''}}}
\def\D{{\mbox{``\$''}}}
\def\F{{\mbox{``F''}}}

\addtolength{\textwidth}{1.5in}
\addtolength{\evensidemargin}{-0.75in}
\addtolength{\oddsidemargin}{-0.75in}
\addtolength{\textheight}{1.0in}
\addtolength{\topmargin}{-0.5in}
\usepackage{epsfig}

\bibliographystyle{plain}

\begin{document}

\hrule

\medskip

\centerline{\large \textbf{Lecture Notes}: Social Networks: Models, Algorithms, and Applications}
\centerline{\textbf{Lecture 1}: Jan 17, 2012}
\centerline{\textbf{Scribes}: Sriram V. Pemmaraju and Rajiv Raman} 

\medskip

\hrule

\section{Introduction}

\paragraph{Max-Coloring.}
Programs that run with stringent memory or timing constraints use a dedicated memory manager that provides
better performance than the general purpose memory management of the operating system. 
The problem we consider here arises in the context of designing memory managers for wireless protocol stacks like
GPRS or 3G. 
With the rapid growth of wireless communication devices, many telecommunication companies now license their 
wireless protocol stacks to vendors of mobile devices.
These protocols stacks have stringent memory requirements as well as soft real-time constraints and
a dedicated memory manager is a natural design choice.
A dedicated memory manager for these stacks must have deterministic response times and use as little
memory as possible. 
The most commonly used memory manager design for this purpose is the {\em segregated buffer pool}. 
This consists of a fixed set of buffers of various sizes with buffers of the same size linked together in a linked
list. 
As each memory request arrives, it is satisfied by a buffer whose size is large enough. 

The similarity between the interval coloring problem and the max-coloring problem can be best understood
by casting these problems into a geometric setting as rectangle packing 
problems.
Start with an interval representation $\{I_v \mid v \in V\}$ of the given interval graph $G = (V, E)$\footnote{Without loss of generality, we assume that the input to our algorithms is a set of weighted intervals.
This is because there are many linear-time algorithms for recognizing interval graphs and most of these
return an interval representation of the given graph, if it is an interval graph.
See \cite{CorneilOlariuStewart} for a recent algorithm.}.
Interpret each weight $w(v)$ as the height of interval $I_v$.
In other words, the instance of the problem consists of axis-parallel rectangles $\{R_v \mid v \in V\}$,
such that the projection of $R_v$ on the $x$-axis is $I_v$ and the height of $R_v$ is $w(v)$.
Each rectangle can be slid up or down but not sideways; all rectangles have to occupy the positive quadrant;
and the regions of the plane they occupy have to be pairwise disjoint.
Given these constraints, 
the interval coloring problem is equivalent to the problem of packing these rectangles so as to minimize the $y$-coordinate of the highest point contained in 
any rectangle.
The max-coloring problem seeks a packing of the rectangles into disjoint 
horizontal strips $S_i = \{(x, y) \mid x \ge 0, \ell_i \le y \le u_i\}$,
denoted by $(\ell_i , u_i)$.
The constraints are that every rectangle is completely contained in some 
strip and for any two rectangles $R_u$ and $R_v$ in a strip, their projections
on the $x$-axis $I_u$ and $I_v$ are disjoint.
Given these constraints, the max-coloring problem seeks a packing 
of the rectangles into strips so that the total height
$\sum (u_i - \ell_i)$ of the strips is minimized.
Figure \ref{fig:rectanglePacking} shows two rectangle packings of a set
of rectangles; the packing on the left is optimal for the interval
coloring problem and the packing on the right is optimal for the max-coloring
problem.
\begin{figure}[htpb]
\epsfysize=1.75in
\centerline{\epsfbox{rectanglePacking.eps}}
\caption{(a) is an interval representation of an interval graph;
the ``name'' and weight of each interval are shown.
(b) is a rectangle packing of this interval graph corresponding to an optimal
interval coloring, with weight 5.
This figure is from \cite{BuchsbaumKarloffKenyonReingoldThorup}.
(c) is a rectangle packing corresponding to an
optimal max-coloring. In the packing on the right the rectangles are packed into 4 strips: $S_1 = (0, 3)$, $S_2 = (3, 4)$, $S_3 = (4, 5)$, and $S_4 = (5, 6)$,
for a total weight of 6.}
\label{fig:rectanglePacking}
\end{figure}

\section{Approximation algorithms for max-coloring}
\label{section:approx}

In an instance of the {\em on-line graph coloring problem}, vertices of a graph
are presented one at a time and when a vertex is presented, all edges connecting
that vertex to previously presented vertices are also revealed.
Each vertex must be assigned a color immediately after it has been presented (and before the next
vertex is presented) and
a color assigned to a vertex cannot be changed later.
An algorithm for the on-line graph coloring problem assigns colors to vertices in the manner described
above, so as to construct a proper vertex coloring of the graph.
We say that an algorithm $A$ for the on-line graph coloring problem $k$-colors a graph $G$, if
no matter which order the vertices of $G$ are presented in, $A$ uses at most $k$ colors to
color $G$. 

Let $A$ be an algorithm for the on-line graph coloring problem. We use $A$ as a ``black-box'' to
devise a simple algorithm for the max-coloring problem.
The algorithm, called {\tt MCA} (short for max-coloring algorithm) is given below.
{\tt
\begin{tabbing}
........\=....\=........\=........\=........\=........\=........\kill\\
\> MCA($G$, $w$)\\
\>\> 1. Sort the vertices of $G$ in non-increasing order of weights.\\
\>\> (Let $(v_1, v_2, \ldots, v_n)$ be this ordering of the vertices of $G$.)\\
\>\> 2. Present the vertices in the order $v_1, v_2, \ldots, v_n$ to $A$.\\
\>\> 3. Return the coloring produced by $A$.
\end{tabbing}}
We will now make a connection between the number of colors used by $A$ and the weight
of the coloring produced by {\tt MCA}.
This connection, along with known results on on-line coloring of interval graphs
will lead to constant factor approximation algorithms for max-coloring for interval graphs.
\begin{theorem}
\label{theorem:connection}
Let ${\cal C}$ be a hereditary class\footnote{A class ${\cal C}$ of graphs is hereditary if
$G \in {\cal C}$ implies that every induced subgraph of $G$ is also in ${\cal C}$.}
of graphs and let $A$ be an algorithm for 
on-line graph coloring such that for some integer constant $c > 0$ and for any graph $G \in {\cal C}$,
$A$ colors $G$ with at most $c \cdot \chi(G)$ colors.
Then, for any $G \in {\cal C}$ and for any weight function $w : V(G) \to \mathbf{N}$,
{\tt MCA} produces a coloring for $G$ whose weight is at most $c \cdot OPT_M(G)$.
\end{theorem}
\begin{proof}
Let $C_1, C_2, \ldots, C_{k}$ be a coloring of $G$ that is optimal for the max-coloring problem.
Let $w_i = \max_{v \in C_i} w(v)$ and without loss of generality assume that 
$w_1 \ge w_2 \ge \cdots \ge w_{k}$.
Now note that $k \ge \chi(G)$ and $OPT_M(G) = \sum_{i = 1}^k w_i$.
Let $A_1, A_2, \ldots, A_t$ be the coloring of $G$ produced by {\tt MCA}.
Let $a_i = \max_{v \in A_i} w(v)$ and without loss of generality assume that $a_1 \ge a_2 \ge \cdots \ge a_t$.
From our hypothesis it follows that $t \le c \cdot \chi(G) \le  c \cdot k$.
For notational convenience, define sets $A_{t+1} = A_{t+2}  = \ldots = A_{c \cdot \chi(G)} = \emptyset$ and
let $a_i = 0$ for $i$, $t < i \le c \cdot \chi(G)$.
We will now claim that for each $i$, $1 \le i \le k$, and each $j$, $c(i-1) < j \le c\cdot i$, we have $w_i \ge a_j$.
Showing this would imply the result we seek because
the coloring produced by {\tt MCA} has weight
$$\sum_{\ell = 1}^{c \cdot \chi(G)} a_{\ell} = \sum_{i = 1}^{\chi(G)} \sum_{j= c(i-1)+1}^{c \cdot i} a_j 
\le \sum_{i = 1}^{\chi(G)} c \cdot w_i \le c \cdot OPT_M(G).$$

Since $w_1$ is the maximum weight of any vertex in $G$, the claim is trivially true for $i = 1$.
For any $i \ge 2$, let $V_i \subseteq V$ be defined as $V_i = \{ v \mid w(v) > w_i\}$.
The coloring $C_1, C_2, \ldots, C_k$ of $G$, restricted to $V_i$ is an 
$(i-1)$-coloring of $G[V_i]$, the subgraph of
$G$ induced by $V_i$.
Because of the order in which vertices are presented to $A$, all vertices in $V_i$ are presented to $A$
before any vertex with weight $w_i$.
Therefore, by our hypothesis, algorithm $A$ colors $G[V_i]$ with no more than $c \cdot (i-1)$ colors.
Therefore, the weight of the heaviest vertex in color classes $A_j$ for $j$, $c(i-1) < j \le c\cdot i-1$ 
is at most $w_i$.
\end{proof}

From this and the induction hypothesis, it follows that
\begin{eqnarray*}
\rs_e(i) & = & \rs_e(j,i) + \rs_e(j-1) \\
         & \geq & \frac{1}{4} (i - j + 1) + 
            \frac{1}{4} (\rs_e(j-1) + \fs_e(j-1)) \\
         & \geq & \frac{1}{4} (\rs_e(j,i) + \fs_e(j,i)) +
                  \frac{1}{4} (\rs_e(j-1) + \fs_e(j-1)) \\
         & =    & \frac{1}{4}  (\rs_e(i) + \fs_e(i))
\end{eqnarray*}

\subsection*{Acknowledgements.} We thank Narayanaswamy and Subhash Babu
for letting us present their clever improvement \cite{NarayanaswamyBabu} of 
our analysis of First-Fit in the preliminary version 
\cite{PemmarajuRamanVaradarajan}.
We also thank Brightwell, Kierstead, and Trotter for
sharing their improved analysis \cite{BrightwellKiersteadTrotter} with us.
Finally, we thank the anonymous referees whose suggestions have 
improved the paper.

{\small
\bibliography{maxcoloring}}

\end{document}
