---
# System prepended metadata

title: 'Exercise 8: Approximate Algorithms'

---

# Exercise 8: Approximate Algorithms
# BR-2

## Q1: Independent Set, Bounded Degree Graph.

* Suppose a node $v$ is selected to be a vertex in the independent set $V'$ by the given algorithm and $v$ is not in $V_{opt}$. Then what is the total number vertices that could be part of $V_{opt}$ instead of $v$?
    **Hint**: Think about a star graph and consider the fact that graph has a bounded degree B.
    
ALG <= OPT
k <= k*B

* Use the above idea to prove that the optimal maximum independent set is at most $B$ times the size of the independent set output by the algorithm. Here $B$ is the bound on the degree of the graph.



## Q2: Probablistic Not all equal Satisfying

* Given a clause $x_1 \vee x_2 \vee x_3$, If we set $x_1,x_2,x_3$ independently at random to value 0 or 1. Then
    * what is the probability that neighter all x_1,x_2,x_3 are true or all of them are false
3/4. 


* The linearity of expectation says that if $A_1,A_2,\ldots,A_k$ are random varaibles then
    * $E[\sum_i A_i] = \sum_i E[A_i]$

c_1 = x_1 \vee x_2 \vee x_3
c_2 = x_1 \vee x_3 \vee x_4

* use the above two ideas to prove that by the randomized greedy algorithm we have
    * $\frac{OPT}{APPROX} = 4/3$

I need a short break
## Q3: Approximaton of Linear Inequalities


* 

## Q4: Approximation of Homogenous Bipolar Inequalities

* For $\text{MAX Hom Bipolar SAT LR}^{\geq}$ Use random assignment ${\bf x}$. Suppose $k$ equations are satisified usign this. How many equations will be satisified using  ${- \bf x}$ if the total equations are $m$?

* How can you modify this algorithm to solve for $\text{MAX Hom Bipolar SAT LR}^{>}$


## Q5: Lower bound of Approximation of Binary Inequalities

Reduce using the Clique Problem.

* Clique(G = (V,E))
   * for each $v_i \in V$, add $x_i$ variable
   * add the equation $i$ as $x_i - \sum\limits_{v_j \in {V \setminus N(v_i)}}x_j$ where $N(v_i)$ is the neighbourhood set of v_i.
    * computeApxSolutionOfAboveEquation
        
* For Proof
    * Notice that if $x_i$ is 1 in the solution, then none of the variables corresponding to $V \setminus N(v_i)$ can be one.
    * Suppose if someone gives you a s-clique $V'$ how can you give you an assignment which satisfies s-equations.
    * Suppose if someone gives you an assignment which satisfies s-equations, can you output s-clique?
    




