<p>As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of <a href="http://epubs.siam.org/doi/10.1137/05064299X" rel="noreferrer">Feige, Hajiaghayi, and Lee</a> is randomized, and no deterministic approximation algorithm with this factor is known. Is this correct? Is any deterministic approximation algorithm with factor below $O(\log OPT)$ known?</p>

CC BY-SA 3.0
2017-05-03T15:21:19.567Z
Are you sure that the FHL algorithm cannot be derandomized?
Chandra Chekuri
CC BY-SA 3.0
2017-05-03T16:01:20.910Z
I'm not sure at all - in fact i would not be *that* surprised if someone points to some paper that derandomizes FHL -- i just haven't been able to find anything like that. If such a derandomization is folklore or follows from a folklore trick i would very much like to know.
daniello
CC BY-SA 3.0
2017-05-03T18:11:35.450Z
I would look at this paper to see if the techniques apply. The ARV rounding is more complicated of course so I am not sure whether it would actually work. http://epubs.siam.org/doi/abs/10.1137/S0097539796309326
Chandra Chekuri
CC BY-SA 3.0
2017-05-09T08:20:37.690Z
Just to be sure I understood the scheme of the FHL algorithm, isn't it that the randomised part lies in the J. Bourgain's result?
M. kanté
<reference-request><approximation-algorithms><derandomization><treewidth>
Deterministic approximation algorithms for treewidth
daniello
# Deterministic approximation algorithms for treewidth

(Asked by: username_0 on 2017-05-02)

As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of [Feige, Hajiaghayi, and Lee](http://epubs.siam.org/doi/10.1137/05064299X) is randomized, and no deterministic approximation algorithm with this factor is known. Is this correct? Is any deterministic approximation algorithm with factor below $O(\log OPT)$ known?

**Tags:** reference-request, approximation-algorithms, derandomization, treewidth
> **Comments:**
> **username_1**: Are you sure that the FHL algorithm cannot be derandomized?  
> **username_0**: I'm not sure at all - in fact i would not be *that* surprised if someone points to some paper that derandomizes FHL -- i just haven't been able to find anything like that. If such a derandomization is folklore or follows from a folklore trick i would very much like to know.  
> **username_1**: I would look at this paper to see if the techniques apply. The ARV rounding is more complicated of course so I am not sure whether it would actually work. http://epubs.siam.org/doi/abs/10.1137/S0097539796309326  
> **username_2**: Just to be sure I understood the scheme of the FHL algorithm, isn't it that the randomised part lies in the J. Bourgain's result?  

---

## 0 answers

