1
$\begingroup$

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.

enter image description here

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!

$\endgroup$
  • 1
    $\begingroup$ A tight example is one in which the approximation ratio is (roughly) 1/2. $\endgroup$ – Yuval Filmus Nov 29 '17 at 14:19
  • $\begingroup$ @YuvalFilmus Thank you Yuval! So, in this case I can show that we have infinite number of edges (as m goes to infinity), then we have ratio of 1/2. $\endgroup$ – user777 Nov 29 '17 at 14:25
  • 1
    $\begingroup$ A tight example (actually, a tight sequence of examples) shows that the algorithm is not a $c$-approximation algorithm for any $c < 1/2$. $\endgroup$ – Yuval Filmus Nov 29 '17 at 14:26
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.