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$
$\endgroup$
4
-
$\begingroup$ Are you sure that the FHL algorithm cannot be derandomized? $\endgroup$– Chandra ChekuriCommented 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$– danielloCommented 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$– Chandra ChekuriCommented 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éCommented May 9, 2017 at 8:20
Add a comment
|