As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of Feige, Hajiaghayi, and Lee 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?

  • $\begingroup$ Are you sure that the FHL algorithm cannot be derandomized? $\endgroup$ May 3, 2017 at 15:21
  • $\begingroup$ 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. $\endgroup$
    – daniello
    May 3, 2017 at 16:01
  • $\begingroup$ 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. epubs.siam.org/doi/abs/10.1137/S0097539796309326 $\endgroup$ May 3, 2017 at 18:11
  • $\begingroup$ 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? $\endgroup$
    – M. kanté
    May 9, 2017 at 8:20


Your Answer

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