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 '17 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 '17 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 '17 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 '17 at 8:20

Your Answer

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

Browse other questions tagged or ask your own question.