Some questions regarding an approximation algorithm for Cardinality Maximum Cut Problem in Vazirani's textbook!

Question

In Vazrani's textbook, page 22, the following exercise:

2.1 Given a n undirected graph G=(V,E), the cardinality maximum cut problem asks for a partition of V into sets S and G\S so that the number of edges running between these sets is maximized. Consider the following greedy algorithm for this problem. Here $v_1$ and $v_2$ are arbitrary vertices in G, and for $A \subset V$, $d(v,A)$ denotes the number of edges running between vertex v and set A.

Show that this is a factor 1/2 approximation algorithm and give a tight example. What is the upper bound on OPT that you are using? Give examples of graphs for which this upper bound is as bad as twice OPT.

First: the upper bound on OPT is easily the number of edges. Second: I have an example of graph that shows that we have 3/5 (so close to 1/2 but not exactly) I tired for several days to find 1/2 but no sign to find one. Now, can I use the limit to show that we have 1/2. i.e. lim as m goes to infinity, $\frac{m/2 + 1}{m} = \frac{m+2}{2m}=1/2$ Is this correct?!! if not, then why! Third: I want to understand the different between "Give examples of graphs to show that this upper bound is as bad as twice OPT" and "tight example"! I mean Are they the same thing?!! For example: tight example would show an approximation ratio 1/2 for this algorithm while "Give examples of graphs to show that this upper bound is as bad as twice OPT" would give 1/2 approximation ratio for this algorithm. Also it seems from the context of the question that "upper bound" we use is not good! do you know any other better upper bound than the number of edges to give a better bound!!

I'm here not to ask for solving problem, instead I just want to understand what the question wants exactly and different between some parts of this question.

Thank you!

Answer 1

An $\alpha$-approximation algorithm $A$ for a maximization problem is an algorithm which on instance $x$ produces a solution $y = A(x)$ of value $V(y) \geq \alpha OPT(x)$, where $V(y)$ is the value of $y$ and $OPT(x)$ is the value of the optimal solution.

A tight instance for such an algorithm is an instance $x$ such that $V(A(x)) = \alpha OPT(x)$. This instance shows that $A$ isn't a $\beta$-approximation algorithm for any $\beta < \alpha$.

In some cases it is impossible to find a single tight instance, yet it is still possible to show that the algorithm isn't a $\beta$-approximation algorithm for any $\beta < \alpha$ using a sequence of solutions $x_i$ satisfying $V(A(x_i))/OPT(x_i) \longrightarrow \alpha$. Such a sequence is sometimes also called a tight instance, even though in reality it is a sequence of instances rather than a single instance.

---

You are also wondering what is the correct answer to the question about which upper bound you are using. Your algorithm presumably uses the trivial upper bound, which is the total number of edges. If you find an "integrality gap" instance in which the ratio between this upper bound and the maximum cut is $\alpha$, then this means that any algorithm using this upper bound cannot have an approximation ratio better than $\alpha$. In your case you can take a large clique, for example (this is actually a sequence of bad instances).

---

The famous Goemans–Williamson algorithm uses a better upper bound, namely the value of a semidefinite relaxation of maximum cut. Using this better upper bound, it manages to increase the approximation ratio from 1/2 to roughly 0.878, which is conjectured to be optimal.