3
$\begingroup$

I am reading The Design of Approximation Algorithms (Williamson and Schmoys; page 50 of this PDF) about solving the minimum-degree spanning tree problem of maximum degree 2 in polynomial time. The text states that we are going to find a tree $T$ with maximum degree at most $2\mathrm{OPT} +\lceil\log_{2} n\rceil$ in polynomial-time. $n$ is the number of the vertices in the graph. Could someone clarify why $\log_{2} n$ is placed there? The text gives no explanation what it is.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

It is $\sf NP$-complete to decide if a given a graph has a minimum-degree spanning tree of maximum degree 2. Because the problem is hard, we would like to compute an approximate solution (to the optimization problem).

What they do is that they show how to find a tree $T$ with $\Delta(T)$ being at most $2\text{OPT} + \log_2 n$. The intuition is that the local search tries to make local improvements to a candidate tree, and when it can't make any improvements, it has found a locally optimal tree. It can then be shown that for any locally optimal tree, the maximum degree is at most $2\text{OPT}+\log_2n$, where $n$ is the number of vertices. The explanation for the logarithmic term is given in Theorem 2.19; it results from a tight analysis.

The best we can hope to do assuming $\sf P \neq NP$ is to find a tree $T$ with $\Delta(T)$ being at most $\text{OPT}+1$. This in fact possible to do, and is shown in a later section of the book.

$\endgroup$
4
  • $\begingroup$ The algorithm is more or less clear but their is one thing that I simply cannot understand. Why is their a logarithm? Other literature could not provide me a answer. Do you know why the logarithm is written their? $\endgroup$
    – Jordi Ozir
    Mar 30, 2014 at 20:41
  • $\begingroup$ @Clifford I believe it's there because it's the best they can show: it could also be $n$, $n^2$, or something that is greater than $\log_2 n$. They simply make a claim and then prove it, so I'm not sure what your exact source of confusion is. Can you clarify? $\endgroup$
    – Juho
    Mar 31, 2014 at 9:04
  • $\begingroup$ Oke the author makes a claim and writes a corresponding proof. Then it does makes sense. So the author claims that there is no solution beter than $2\text{OPT}+\log_2n$. $\endgroup$
    – Jordi Ozir
    Mar 31, 2014 at 9:16
  • $\begingroup$ @Clifford "So the author claims there is no solution better than..." well, not exactly. They only say: "this algorithm here gives us a solution that is no worse than $2\text{OPT} + \log_2 n$, but who knows, maybe there are way better algorithms". (And actually, there are!) $\endgroup$
    – Juho
    Mar 31, 2014 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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