Some questions regarding an approximation algorithm for Cardinality Maximum Cut Problem in Vazirani's textbook!
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 &lt; \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 &lt; \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&ndash;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.