\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{algorithm2e, setspace}
\usepackage[colorlinks = false]{hyperref}
\usepackage{float}
\usepackage{subcaption}
\usepackage{mathtools}

\newcommand{\1}{\mathbbm{1}}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\newcommand{\x}{\times}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\E}{\mathop{\mathbb{E}}}
\newcommand{\Scomp}{\overline{S}}
\renewcommand{\bar}{\overline}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\eps}{\varepsilon}

\newcommand{\DTIME}{\textbf{DTIME}}
\renewcommand{\P}{\textbf{P}}
\newcommand{\SPACE}{\textbf{SPACE}}
\setlength{\parskip}{8pt}%
\setlength{\parindent}{0pt}%

\begin{document}
\setlength{\parindent}{0pt}
\RestyleAlgo{boxruled}
\input{preamble.tex}

\newtheorem{example}[theorem]{Example}
\theoremstyle{definition}
\newtheorem{defn}[theorem]{Definition}
\handout{E0 249: Approximation Algorithms}{Feb 28, 2022}{Instructor: Arindam Khan, Anand Louis
}{Scribe: Sarvagya Jain, Prashant Gokhale}{Geometric Approximation Week 2}



\section{Technique 4: Seperators}

\begin{theorem}[Planar Seperator Theorem (Lipton - Tarjan '77)]

The informal idea is that any planar graph can be split into smaller but balanced pieces by removing a small number of vertices. Given a planar graph $G = (V,E)$, $|V| = n$, we can partition $V$ into $V_1$, $V_2$ and $X$ such that 

\begin{itemize}
    \item $\delta V_i \subset X$ (for $i=1,2$)
    \item $\frac{1}{3}n \leq |V_i| \leq \frac{2}{3}n$ (for $i=1,2$)
    \item $|X| \leq O(\sqrt{n})$
\end{itemize}

(from here on the notation $ \delta V_i$ means all neighbours of $V_i$ excluding $V_i$)
\end{theorem}

\begin{figure}[H]
\centering
    \includegraphics[scale=0.2]{imaget1.png}
    \caption{Planar seperator for grid}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[scale=0.6]{septhm.png}
    \caption{Planar seperator from circle packing}
\end{figure}



\begin{theorem}[Geometric Seperator Theorem (Smith Wormald '98)]
    This theorem extends the planar graph case. Given $n$ disjoint disks (or squares or fat objects), there exists a square $B$ such that, 
    
    \begin{itemize}
        \item Number of items inside $B$ $\leq \frac{4}{5}n$
        \item Objects outside $B$ $\leq \frac{4}{5}n$
        \item Objects intersecting $\delta B$ $\leq O(\sqrt{n})$ (in case of the $d$-dim variant this is $O\left(n^{1 - \frac{1}{d}}\right)$)
    \end{itemize}
\end{theorem}
    
\begin{proof}
    Let $B_0$ be the smallest square containing $\geq \frac{n}{5}$ center points. Let $r$ be the side length of $B_0$. 
    
    Let $B$ be a randomly shifted square of side length $ \left(2 - \epsilon \right) r$ that contains $B_0$. 
    
    $B$ can be covered by four copies of $B_0$. As, $B_0$ was smallest square containing $\geq \frac{n}{5}$ points, we must have number of center points inside $B$ to be $\leq \frac{4}{5}n$ (since $B$ can be divided into $(1-\epsilon)r$ side squares). Also we have number of center points $\geq \frac{1}{5} n$ since $B_0 \subset B$. 
    
    \begin{figure}[H]
    \centering
    \includegraphics[scale=0.3]{proofstep.pdf}
    \caption{$B$ can be covered by $4$ copies of $B_0$}
    \label{gcbin}
\end{figure}
    
    \textbf{Case 1:} Consider an object $S$ of radius $\leq \frac{r}{k}$. We have $\mathbb{P}[\text{S intersects $\delta B$}] \leq O \left(\frac{r}{kr} \right) = O\left(\frac{1}{k}\right)$
    
    This gives us,
    
    $$\mathbb{E}[\text{number of objects of radius $\leq \frac{r}{k}$ intersecting $\delta B$}] \leq O\left( \frac{n}{k} \right)$$
    
    \textbf{Case 2: } Consider objects of radius $> \frac{r}{k}$. Number of such objects intersecting $\delta B$ is $\leq O(k)$. 
    
    Comining both cases We get,
    
    $$\mathbb{E}[\text{number of objects intersecting $delta B$}] \leq O\left( \frac{n}{k} + k \right)$$
    
    Setting $k = \sqrt{n}$,
    
    $$\mathbb{E}[\text{number of objects intersecting $delta B$}] \leq O\left( \sqrt{n} \right)$$    
\end{proof}


\section{PTAS for independent set for disks (Chan '03)}

First of all, we will need a more general seperator theorem stated below. 

\begin{theorem}[General Seperator Theorem]

Consider a measure $\mu(.)$ that maps a collection of objects to a non-negative number and satisfies the following axioms:

\begin{itemize}
    \item If $A \subset B$, then $\mu(A) \leq \mu(B)$
    \item $\mu(A \cup B) \leq \mu(A) + \mu(B)$
    \item If no pair of objects in $A \times B$ intersects, then $\mu(A \cup B) = \mu(A) + \mu(B)$
    \item Given any $r$ and size $r$ box $R$, if every object in $A$ intersects $R$ and has size at least $r$, then $\mu(A) \leq c$ for a constant $c$.
    \item A constant-factor approximation to $\mu(A)$ can be computed in time $|A|^{O(1)}$. If $\mu(A) \leq b$, then $\mu(A)$ can be computed exactly in time $|A|^{O(b)}$ and linear space.
\end{itemize}

\textbf{Example: } independent set (S), piercing(S)
     
     
    Given a measure $\mu$ satsisfying the above axioms and a collection $C$ of $n$ objects in $\mathbb{R}^{d}$ with $\mu(C)$ sufficiently large, there exists a box $R$ such that $\mu(C_R) \geq \alpha \mu(C)$, and $\mu(C|_{\delta R}) = O \left( \mu\left( C\right)^{1-\frac{1}{d}}\right)$, where $\alpha > 0$ is some fixed constant. Moreover, if the last axiom above is satisfied, such a box can be found in polynomial time and linear space.
\end{theorem}

Now, we describe the algorithm. Fix a constant $b$. Let $OPT(I) = \text{max independent set}$.

\begin{algorithm}[H]
\setstretch{1.15}
\SetAlgoLined
\KwData{Set of disks}
\KwResult{Approximation of Maximum Independent Set}

\If{$OPT(I) \leq b$}
{
    Solve in $n^{O(b)}$ time by brute forcing.
}

\Else
{
    Find square $B$ such that $OPT(\text{object inside $B$}) \geq \frac{OPT(I)}{5^{\beta}}$ (use $\beta$ approx on OPT eg. greedy), $OPT(\text{object outside $B$}) \geq \frac{OPT(I)}{5^{\beta}}$ (use $\beta$ approx on OPT eg. greedy), $OPT(\text{objects intersecting $\delta B$}) = O(\sqrt{OPT(D)})$
}

Recurse on {objects inside B}, {objects outside B}. 

\caption{Approximation of MIS for set of disks}
\end{algorithm}

\textbf{Analysis:} Additive error is $m$ for an instance $\mu(C) = m$, 

If $m > b$ then for some $m_1, m_2 \geq \frac{m}{5\beta}$ and $m_1 +m_2 \leq m$ we have,
$$E_r(m) \leq E_r(m_1) + E_r(m_2) + O(\sqrt{m})$$

If $m \leq b$, then we have,

$$ E_r(m) = 0$$

Thus, we get $E_r(m) = O(\frac{m}{\sqrt{b}})$.

So the approx factor is $\left( 1 + O(\frac{1}{\sqrt{b}}) \right)$. Set $b = \frac{1}{\epsilon^2}$. This gives us a $(1+ \epsilon)$ approximation in $n^{O(\frac{1}{\epsilon^2})}$ time. 

\textbf{Remark: } The measure $\mu$ makes the technique quite general and thus extends to piercing etc. also.

\section{Maximum Independent set of line segments}

\textbf{Special Case: } Axis Parallel

There is a simple $2$-approximation for this case.

\begin{itemize}
    \item Consider only vertical or only horizontal lines. 
    \item Each can be solved exactly using max independent set of intervals.
    \item Return the best of these two max independent sets. 
\end{itemize}

This will be a two approximation since at least one of them will return a set better than $\frac{OPT}{2}$.

Surprisingly, $(2 + \epsilon)$ is the best known approximation for max independent set of (axis-parallel) rectangles. [Galvez et al., 2021].

However, for arbitrary (may not be axis parallel) line segments the best known approximation ratio is $n^{\epsilon}$ [Fox-Pach]. 

\begin{lemma}[Fox-Pach]
    For intersection graph of $n$ line segments $S$ in $\mathbb{R}^2$ with $m$ intersections, there exists a partition of $S$ into $S_1, S_2, X$ such that $|S_1|, |S_2| \leq \frac{2n}{3}$, $S_1 \cap S_2 = \phi$, $|X|$ is $O(\sqrt{m})$.

    In short this lemma says that sparse graph implies a good separator. This can be extended to the case for arbitrary curves such that each pair intersects $O(1)$ times.

\end{lemma}

\textbf{Proof Idea:} If a curve has $k$ intersection points, add weight $\frac{1}{k}$ to each. Then apply weighted Lipton-Tarjan planar separator theorem with intersection points as vertices. 

\begin{lemma}[Fox-Pach]
    For intersection graph of $n$ curves $S$ in $\mathbb{R}^2$ (each pair intersects $O(1)$ times), if number of intersection $m > \delta n^2$, then there exists disjoint subsets $A,B \subset S$ of size $\geq \delta n$ such that every curve in $A$ intersects every curve in $B$. 
    
    In short, this lemma says that dense graph implies large balanced bi-clique.
\end{lemma}

\textbf{Observation: } No independent set in $S$ can contain both a segment in $A$ and a segment in $B$. So, every independent set is contained in $S \setminus A$ or $S \setminus B$ implies $OPT(S) \subset S \setminus A$ or $OPT(S) \subset S \setminus B$.


\begin{algorithm}[H]
\setstretch{1.15}
\SetAlgoLined
\KwData{Set of line segments}
\KwResult{Approximation of Maximum Independent Set}

\textbf{Case 1:} $m \leq \delta n^2$ (sparse). Apply lemma 4 to get $S_1, S_2, X$. Recurse in $S_1, S_2, X$ to get $I(S_1), I(S_2), I(X)$. Return larger of $I(S_1) \cup I(S_2)$ and $I(X)$.

\textbf{Case 2:} $m > \delta n^2$ (dense). Apply lemma 5 to get $A,B$. Recurse in $S \setminus A$, $S \setminus B$ to get $I(S \setminus A)$, $I(S \setminus B)$. Return larger of $I(S \setminus A)$ and $I(S \setminus B)$. 

\caption{Fox-Pach}
\end{algorithm}

\textbf{Analysis: }

Approximation ratio: we want to show that $|OPT(S)| \leq f(n) |I(S)|$. 

\textbf{Case 1:} 

$$|OPT(S)| \leq |OPT(S) \cap S_1| + |OPT(S) \cap S_2| + |OPT(S) \cap X|$$

$$\leq f(\frac{2n}{3}) |I(S_1)| + f(
\frac{2n}{3}) |I(S_2) + f(\sqrt{\delta n}) |I(x)| \leq f(\frac{2n}{3})|I(S_1) \cup I(S_2)| + f(\sqrt{\delta n}) |I(X)| \leq [f(\frac{2n}{3}) + f(\sqrt{\delta}n)] |I(S)|$$

\textbf{Case 2: }

$$|OPT(S)| \leq max\{ |OPT(S-A)|, |OPT(S-B)| \} \leq max\{ f(n-\delta n) |I(S-A)|, f(n-\delta n) |I(S-B)|\} \leq f(n -\delta n) |I(S)|$$


Set $f(\frac{2n}{3}) + f(\sqrt{\delta}n) \approx f(n - \delta n)$. Assume $\delta$ is sufficiently small, then we have $f(n) = n^{\epsilon}$. Thus, we get a $n^{\epsilon}$ approximation.

Now, we analyze the runtime. 

\textbf{Case 1: }
$$T(n) \leq T(n_1) + T(n_2) + T(X) + poly(n)$$

\textbf{Case 2: }

$$T(n) \leq 2T((1-\delta)n) + poly(n)$$

Thus, we have polynomial runtime.

\section{Local Search}

This technique will give us PTAS for independent set for fat objects. Fix $b$. 

\begin{itemize}
    \item Initialise $T = \phi$ (or any feasible solution). Repeat the following until stuck,
    \item For each subset $D \subset T$ of size $\leq b$ and $S \subset I - T$ of size $|D| + 1$ do: If $(T-D) \cup S$ is a feasible solution $T$ is assigned as $(T-D) \cup S$.
    \item Return $T$.
\end{itemize}

\textbf{Analysis: }

First, we analyse the runtime. Number of iterations is clearly $O(n)$. Time per iteration is $O(n^{b+b+1+2}) = n^{O(b)}$

\textbf{Analysis: }[Chan-HarPeled '09]

We need a multi cluster version of Smith-Wormald's seperator theorem. 

\begin{theorem}
Given intersection graph of $n$ constant depth fat objects in $\mathbb{R}^2$, we can partition into  $V_1$, $V_2$ ... $V_{O(\frac{n}{b})}$, $X$ such that, $\delta V_i \subset X$, $|V_i \cup \delta V_i| \leq b$, $|X| \leq O(\frac{n}{\sqrt{b}})$ and $\sum |\delta V_i| \leq O(\frac{n}{\sqrt{b}})$
\end{theorem}

Let $T^*$ be optimally independent set and
$T$ be locally optimum independent set.

Now, apply above theorem to $T^* \cup T$ (depth = 2).

Then, $|T^* \cap V_i| \leq |T \cap (V_i \cup \delta V_i)|$ (else we can delete $T cap (V_i \cup \delta V_i)$ from $T$ and insert $T^* \cap V_i$ to get larger independent set).

Hence,

$$\sum_i |T^* \cap V_i| \leq \sum_i |T \cap V_i| + \sum_i |\delta V_i|$$.

Now, 

$$|T^*| \leq \sum_i |T^* \cap V_i| + |T^* \cap X| \leq \sum_i |T \cap V_i| + \sum_i |\delta V_i| + |T^* \cap X|  \leq |T| + O(\frac{|T \cup T^*|}{\sqrt{b}}) \leq O(\frac{|T| + ||T^*}{\sqrt{b}})$$

Simplyfying, we get,

$$|T^*| \leq |T| (1+O(\frac{1}{\sqrt{b}})) (1 -  O(\frac{1}{\sqrt{b}}))^-1 \leq |T| (1 + O(\frac{1}{\sqrt{b}}))$$

Setting $b = \frac{1}{\epsilon^2}$, we obtain $(1+\epsilon)$ approximation in $n^{O(\frac{1}{\epsilon^2})}$ time. 

Note that this also works for pseudodisks (set of objects such that boundary of each pair
intersects at most twice).

\section{Linear Programming}

We will use linear programming to give an $O(\log(\log{n}))$-approximation algorithm for maximum weighted independent set of rectangles (MWISR). 

Recall the following definitions: 

\begin{itemize}
    \item Independence (stability) number $\alpha(F)$: maximum number of pairwise disjoint sets in $F$.
    \item Clique number $\omega(F)$: maximum number of pairwise intersecting sets in $F$. 
    \item Coloring number $\chi(F)$ or $d(F)$: minimum number of classes in a partition of $F$ into pairwise disjoint sets.
\end{itemize}

The relations between these numbers are very important in combinatorics and theoretical computer science. Some known results and conjectures regarding these numbers for families of rectangles are as follows:

\begin{itemize}
    \item $\chi\leq 4 \omega (\omega - 1)$ [Asplund and Gr{\"u}nbaum]
    \item $\chi \leq O(\omega \log{\omega})$ [Chalermsook and Walczak, SODA '21]
    \item $\chi = O(\omega)$ [conjecture]
\end{itemize}

We outline the proof of the fact that $\chi \leq 4 \omega (\omega - 1)$. Let $\mathcal{R}$ denote the family of rectangles. We first classify the ways in which two rectangles $R$ and $R'$ in $\mathcal{R}$ can intersect. 

\begin{itemize}
    \item Corner intersection: $R$ contains at least one corner of $R'$ and vice versa.
    \item Crossing intersection: If 
    $R$ and $R'$ intersect but it's not a corner intersection.
    \item Containment intersection: One rectangle contains the other (this is a special case of corner intersection).
    \item Vertical intersection: If one rectangle intersects both the top and bottom sides of the other.
\end{itemize}

For a rectangle $R$, we let $V(R)$ denote the set of rectangles that intersect both the
bottom and top sides of $R$ and $X(R)$ denote the set of rectangles that cross $R$.

\begin{definition}[$s$-sparse]
A family of rectangles $\mathcal{R}$ is $s$-sparse if we can fix $s$ points $p_1^R$, $p_2^R$ ... $p_s^R$ in each $R \in \mathcal{R}$ such that for all crossing rectangles $R, R' \in \mathcal{R}$ we have the property that $R \cap R'$ contains at least one of $\{ p_1^R, p_2^R ... p_1^{R'}, p_2^{R'}... \}$.
\end{definition}

For example, a family of squares is $0$-sparse as it is crossing free. 

We will now prove a technical lemma which will help us get a bound on the coloring number of rectangle families that are crossing free. 

\begin{lemma}
    Every $s$-sparse family of rectangles with clique number $\omega$ is $(2s +4) (\omega - 1)$ - colorable in polynomial time. 
\end{lemma}

\begin{proof}
    First we show that the number of edges in the intersection graph $G$ is strictly less than $(s+2)(\omega -1 ) |\mathcal{R}|$ by token counting. If $R$ and $R'$ cross, give one token to a point in the set $\{p_1^R, \dots, p_s^R, p_1^{R'}, \dots, p_S^{R'}\}$ that lies in $R \cap R'$. If $R$ and $R'$ have corner intersection, give $\frac{1}{2}$ tokens to the two corners involved in the intersection. Clearly, total number of tokens is equal to the number of edges. 
    
    Total amount of received tokens by points is strictly less than $|\mathcal{R}|\left(s(\omega-1)+4\frac{\omega-1}{2}\right)=|\mathcal{R}|(s+2)(\omega-1)$. The first term comes because each point $p_i^R$ receives at most $\omega-1$ tokens and the second term comes because each of the four corners can receive at most $\frac{\omega-1}{2}$ tokens with some corners receiving strictly fewer tokens (for example, the left most corner among the top edges). Therefore, the number of edges is strictly less than $|\mathcal{R}|(s+2)(\omega-1)$.

Now we use induction on $|\mathcal{R}|$ to show the $(2s+4)(\omega-1)$-colorability.

For the base case, we use the case when $|\mathcal{R}|=2$. As the number of edges is non-negative, the bound on number of edges implies that $\omega\geq 2$. Trivially this family can be colored using only $2$ colors which is less than $(2s+4)(\omega-1)$ colors (we used $s\geq 0$ and $\omega\geq 2$). For the inductive step, using pigeon hole principle we note that there exists a vertex $v$ of degree strictly less than $\frac{2(s+2)(\omega-1)|\mathcal{R}|}{|\mathcal{R}|} = (2s+4)(\omega-1)$.  Using the induction hypothesis, $G\setminus \{v\}$ can be colored using $(2s+4)(\omega-1)$ colors. As the vertex $v$ has strictly less than $(2s+4)(\omega-1)$ neighbours, we can color it with one of the $(2s+4)(\omega-1)$ colors as well. Thus, $G$ is $(2s+4)(\omega-1)$ colorable.
\end{proof}

Since for crossing free rectangle families are $0$-sparse, hence we get the following corollary: 

\begin{corollary}
Every family of rectangles with no crossing intersections (only corner/ containment intersections) are $4(\omega-1)$-colorable.
\end{corollary}

We need the following result from combinatorics, which we state without proof:

\begin{theorem}[Mirsky's Theorem]
 For every finite poset the height equals the minimum number of antichains (subsets in which no pair of elements are ordered) into which the poset can be partitioned.
\end{theorem}

\begin{figure}[H]
\centering
    \includegraphics[scale=0.6]{dilworth1.png}
    \caption{A poset of height $h$ can be partitioned into $h$ antichains}
\end{figure}

We also state a result similar to the one stated above:
\begin{theorem}[Dilworth's Theorem]
Maximum size of an antichain (known as width of the poset) is equal to the minimum number of chains in the partition of poset into chains.
\end{theorem}

\begin{figure}[H]
\centering
    \includegraphics[scale=0.6]{dilworth2.PNG}
    \caption{Planar seperator for grid}
\end{figure}

Finally, we are ready to prove the identity in consideration.

\begin{theorem}
$\mathcal{R}$ is $4\omega(\omega-1)$-colorable.
\end{theorem} 

\begin{proof}
    Define a partial order $\prec$ on $\mathcal{R}$ such that $R\prec R'$ if and only if $R'\in X(R)$. Every chain (subset of poset that is totally ordered) in this poset $(\mathcal{R}, \prec)$ is a clique in $\mathcal{R}$. So the height (maximum cardinality of a chain in a poset) of $(\mathcal{R}, \prec)$ is at most $\omega$. 



Now using Mirsky's theorem, $\mathcal{R}$ can be partitioned into $\omega$ antichains. As each crossing is crossing free, from the above corollary we get that $\mathcal{R}$ is $4\omega(\omega-1)$ colorable.
\end{proof}


The following theorem, which we state without proof, is a stronger result due to Chalermsook and Walczak.
\begin{theorem}
$\mathcal{R}$ is $O(\omega\log \omega)$-colorable.
\end{theorem}

In special cases, one can obtain better bounds:
\begin{itemize}
    \item Only crossing and containment intersections: $\chi(\mathcal{R}) = \omega(\mathcal{R})$
    \item Only vertical intersections: $\chi(\mathcal{R})\leq 3\omega(\mathcal{R})-2$

\end{itemize}
Now we will try to get a relation between $\alpha$ and $\omega$.


We start by preprocessing to ensure that all weights $w_R\in \{0, 1, 2, \dots, 2n\}$ $\forall R\in \mathcal{R}$ (here $n$ is the number of rectangles). To do this, scale weights such that $\min_{R\in \mathcal{R}} w_R = 1$, let $w_{\max} = \max_{R\in \mathcal{R}} w_R$ and finally define new weight $\hat{w}_R = \floor{w_R\frac{2n}{w_{\max}}}$. 

We claim that any $r$-approximate solution for $\hat{w}_{R}$ is $2r$-approximate solution for $w_R$. To see this, for any set $S\subseteq \mathcal{R}$, we have $\sum_{R\in S}w_R\frac{n}{w_{\max}}\leq \sum_{R\in S}\hat{w}_R\leq w_R\frac{2n}{w_{\max}}$. In particular, $\sum_{R\in OPT}w_R\frac{n}{w_{\max}}\leq \sum_{R\in OPT}\hat{w}_R\leq r\sum_{R\in ALGO}\hat{w}_R\leq r\sum_{R\in ALGO}w_R\frac{2n}{w_{\max}}$. This gives, $\sum_{R\in OPT}w_R\leq 2r\sum_{R\in ALGO}w_R$. 

So from now on we will assume that all weights are in $\{0, 1, \dots, 2n\}$ (as shown above, we lose only a factor of $2$ by doing this). In fact, we can remove rectangles that have new weight being $0$. Note their original total weight is small as $\hat{w}_R=0$ if and only if $w_R\leq w_{\max}/2n$. This implies that $\sum_{R:\hat{w}_R = 0}\leq w_{\max}/2$.


We consider the clique-constrained LP relaxation for MWISR. Let $\mathcal{R}$ represent the family of $n$ rectangles, $w_R$ represents the weight of rectangle $R\in \mathcal{R}$ ($w_R\in\{1, \dots, 2n\}$). $F$ represents the family of inclusion maximal cliques in $\mathcal{R}$. With this notation, the LP we consider is as follows:

$$\begin{array}{ccc}
\max & \sum_{R\in\mathcal{R}}w_Rx_R & \\
\text { s.t. } & \sum_{R\in C}x_R\leq 1 & \forall C\in F \\
&x_R\geq 0& \forall R\in \mathcal{R}\end{array}$$




Let $(x_R^{*})_{R\in \mathcal{R}}$ represent the optimum fractional solution to the LP and let $w^*$ represent the optimum LP value of the optimum solution. 

We observe that $|F|\leq n^2$. This is because, intersection of every inclusion maximal clique is a rectangle whose top left corner is the intersection point of the top side of some rectangle in $\mathcal{R}$ with the left side of some rectangle in $\mathcal{R}$.

We break the problem into two cases.

\textbf{Case 1:} $w^*$ is $O(n)$

Just output the maximum weight rectangle. Weight is at least $2n$ which implies that we already have an $O(1)$-approximation.

\textbf{Case 2:} $w^*\geq 32n$. 

Take $M=64\log n$. We will convert $(x_R^*)_{R\in\mathcal{R}}$ into a solution $(x_{R}')_{R\in \mathcal{R}}$ which is $1/M$-integral (i.e., $x_R' = k/M, k\in \{0, \dots, M-1\}$) and $\sum_{R\in\mathcal{R}w_Rx_R'}$ is $\Omega(w^*)$.


\begin{lemma}
    Given $w^* \geq 32n$, there exists a polynomial time algorithm which produces a feasible solution $(x_{R}')_{R\in \mathcal{R}}$ to our LP such that:
    \begin{enumerate}
        \item $x^*_r $ is $\frac{1}{M}$ integral, and
        \item $\sum_{R \in \mathcal{R}}$ $w_Rx'_R$ is $\Omega(w^*)$.
    \end{enumerate}
\end{lemma}
\begin{proof}
    First, we will create a multiset $\tilde{\mathcal{R}}$ from $\mathcal{R}$. For each $R \in \mathcal{R}$, create ($\ceil{x_R M} - 1$) copies of $R$ with value of corresponding LP variable being $\frac{1}{M}$ and one copy with corresponding LP variable value being $x_R - \frac{\ceil{x_R M}-1}{M}$. Call this LP solution $\tilde{x}$. Let $T_R$ be the set of ($\ceil{x_RM} -1$) copies of R. Define $\Tilde{x}_R := \sum_{t \in T_R} \Tilde{x}_t$. As $\tilde{x}_R = x_R$, clearly $\tilde{x_R}$ is a feasible solution of the LP.
    
    Now create multiset $\mathcal{R}'$ from $\Tilde{\mathcal{R}}$ by selecting each copy of $R\in \Tilde{\mathcal{R}}$ independently with probability $\frac{M}{2}\Tilde{x_R}$.
    
    Define $x'$ to be a "candidate" LP solution if each selected copy is assigned a value of $\frac{1}{M}$. And if $t$ copies of rectangle $R$ are selected in $\mathcal{R}'$ then set $x_R' = \frac{t}{M} $. So, $(1)$ is trivially true, i.e $x_R'$ is $\frac{1}{M}$-integral.
    
    Now, we show that $x'$ feasible for LP with high probability.
        Let $C\in F$. Let $C'$ be the subset of rectangles of $C$ that are present in $\mathcal{R}'$.
        Then,
        \[ \E[|C'|] = \E[\sum_{R \in C} \sum_{t \in T_R} \P [\text{copy $t$ of rectangle $R$ was selected in } \mathcal{R}']]\]\[= \sum_{R \in C} [\sum_{t \in T_R} \frac{M}{2} \Tilde{x}_t]=\frac{M}{2}[\sum_{R \in C}\sum_{t \in T_R} \Tilde{x_t}]= \frac{M}{2}[\sum_{R \in C} \Tilde{x_R}]\leq \frac{M}{2}\]
        
        The last inequality follows from the fact that $\tilde{x}$ is a feasible solution.
      
        Now we will use Chernoff Bound to show concentration. From a variant of Chernoff bound, we have that for a sum of independent $0-1$ random variable $Z$, we have $\P[Z>2\E[Z]]<\exp(-\E[Z]/3)$. Using this bound, we get
        \[\P[|C'|>M]\leq \exp(-M/6)\leq 1/n^4.\]
        
        The last inequality follows as we chose $M$ to be $64\log n$.
        
        Hence $\P[\sum_{R\in C'}x_{R}'>1] = \P[|C'|/M>1] = \P[|C'|>M]\leq 1/n^4$.
        
        Applying union bound over $F$ (recall that $|F|\leq n^2$), we get that $\sum_{R\in C'}x_{R}'\leq 1$ $\forall C\in F$ with probability at least $1-1/n^2$. Hence, $x'$ is feasible with probability at least $1-1/n^2$.

    
    For $(2)$, we divide the rectangles in $\tilde{\mathcal{R}}$ into $\ceil{\log (2n)}$ subcollections $\{\mathcal{R}'\}_{i=1}^k$, where $\tilde{\mathcal{R}}_i = \{R\in \tilde{\mathcal{R}}: w_R\in [2^{i-1}, 2^i)\}$. Partition $\mathcal{R}'$ into $\{\mathcal{R}'_i\}_{i=1}^k$ similarly. Hence, $\E[|\mathcal{R}'_{i}|] = \sum_{R\in\tilde{\mathcal{R}}_{i}}\sum_{t\in T_R}\P[t \text{ is selected in }\mathcal{R}'] = \sum_{R\in\tilde{\mathcal{R}_{i}}}\frac{M}{2}\tilde{x}_R = \frac{M}{2}\sum_{R\in\tilde{\mathcal{R}_{i}}}\tilde{x}_R$.
    
    
    Define $i \in[k]$ bad if and only if $\sum_{R \in \tilde{\mathcal{R}}_{i}} \tilde{x}_{R}<4$, otherwise define $i$ to be good.
Let $B$ be set of bad indices.
Now we claim that $\sum_{i \in B} \sum_{R \in \tilde{\mathcal{R}}_{i}} w_{R} \tilde{x}_{R} \leq w^{*} / 2$. To see this,
$\sum_{R \in \tilde{\mathcal{R}}_{i}} w_{R} \tilde{x_{R}}<2^{i} \sum_{R \in \mathcal{R}_{i}} \tilde{x}_{R}<4\cdot 2^{i}$.
Summing over all $i \in B$,
$\sum_{i \in B} 4 \cdot 2^{i} \leq \sum_{i=1}^{k} 4 \cdot 2^{i} \leq 16 n \leq w^{*} / 2 .$
For good indices $i \not\in B$, $E[ |R'_{i}|]
\geq \frac{M}{2}\left(\sum_{R \in \tilde{\mathcal{R}}_{i}} \tilde{x}_{R}\right) \geq \frac{M}{2} \cdot 4=2 M .
$

Using Chernoff bound,
$\P[|\mathcal{R}'_{i}| \leq \frac{M}{4} \cdot\left(\sum_{R \in \tilde{\mathcal{R}}_{i}} \tilde{x}_{R}\right)] \leq \P[|\mathcal{R}'_{i}| \leq \frac{\E[R'_{i}]}{2}]
\leq e^{-\E[R'] / 8} \leq e^{-2 M / 8} \leq e^{-16 \log n}=\frac{1}{n^{16}}.$
Thus, using union bound,
$|\mathcal{R}'_{i}| \geq \frac{M}{4}\left(\sum_{R \in \tilde{\mathcal{R}}_{i}}{\tilde{x_{R}}}\right)\;\forall i \notin B$ with high probability.
    
So, $\sum_{R \in \mathcal{R}'_{i}} x'_{R} \geq \sum_{R \in \tilde{\mathcal{R}}_i} \tilde{x}_{R} / 4$. For each $i \notin B$, we have:
$$
\sum_{R \in \mathcal{R}'_{i}} w_{R} x'_{R} \geq \frac{2^{i-1}}{4} \sum_{R \in \tilde{\mathcal{R}}_{i}} \tilde{x}_{R} \geq \frac{1}{8} \sum_{R \in \tilde{\mathcal{R}}_{i}} x_{R} w_{R} .
$$
Summing over all $i \notin B$, we get $\sum_{i k B} \sum_{R \in \mathcal{R}'_{i}} w_{R} x'_{R} \geq \frac{1}{8} \sum_{i \notin B}\sum_{R \in \tilde{\mathcal{R}}_{i}} x_{R} w_{R} \geq \frac{1}{8}\frac{w^{*}}{2}=w^*/ 16$.


Given LP solution,  $\left(x_{R}^{\prime}\right)_{R \in R}$, we create multiset $\mathcal{R}''$ : for each $R \in \mathcal{R}$, add $C_{R}:= M x'_{R}$ copies of $R$ to $R$ ".\\
As each copy in $R'$ has LP weight $\frac{1}{M}$, maximum clique size by this is $\leq M$. Also, $\sum_{R \in \mathcal{R}} w_{R} x_{R}$ is $\Omega\left(w^{*}\right)$. Hence, $\mathcal{R}''$ can be coloured using $O(M \log M$ ) colors. So, maximum weight color class has weight $\geq \frac{\Omega\left(w^{*}\right) M}{O(M \log M)}\geq \Omega\left(w^{*} / \log M\right)$
 As $OPT\leq w^{*}$ and $M$ is $\Theta(\log n)$, we get $O(\log \log n)$-approximation.
    

\end{proof}
\end{document}
