65 Approximation algorithms and Randomised algorithms

Approximation Algorithm

Example

Given an undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges, find a set $X\subseteq V$ which maximises the number of edges with one end-point in $X$ and other endpoint in $V\setminus X$

• Can we find a set $Y$ such that the number of edges between $Y$ and $V\setminus Y$ is at least $1/2$ times that of the maximum possible ?
• $\cdots$ in $n^{O(1)}$ time

Lets have a graph $G$ with vertex for each student $u-v$, if $u$ and $v$ do not know each other

• Start with any partition $Y$ and $V\setminus Y$

• If $\exists x\in Y$ with strictly more neighbours in $Y$ then in $V\setminus Y$ then move $x$ to $V\setminus Y$

• If $\exists x\in V\setminus Y$ with strictly more neighbours in $V\setminus Y$ then move $x$ to $Y$

• When this process stops, each vertices has $\ge$ half its neighbours across

• This implies that the cut $\ge |E|/2$

• We have designed $1/2$ approximation for Max Cut in $n^{O(1)}$ time

Using Randomisation

• Put $x$ in $L$ with probability $0.5$ & $x$ in $R$ with probability $0.5$
• $\forall$ edges $a,b$, $P[\text{ab in cut}]=0.5$
• Expected number of edges $=\frac{|E|}{2}$ (linearity of expectations)
• $\exists$ cut of $\ge =\frac{|E|}{2}$ (budget of expectations)

Max $3$-SAT

Example

Given an instance of $3$-SAT with $N$ variables and $M$ clauses, find the minimum number of clauses that can be satisfied by any truth assignment

• $3$-SAT is the restriction of SAT where each clause has at most $3$ literals
• For simplicity, here we can assume exactly 3 literals

Using Randomisation

Put $x=T$ with probability $0.5$ and $x=F$ with probability $0.5$, for each variable $x$

$P[\text{C is satisfied}]=7/8$
Expected number of clauses satisfied $=\frac{7M}{8}$
$\exists$ assignment satisfying $\ge \frac{7M}{8}$ clauses