7
$\begingroup$

Leighton, Rao presented an $O(\log n)$ approximation algorithm for directed and undirected balanced vertex separator. Agarwal, Charikar, Makarychev, Makarychev improved this approximation factor of directed balanced vertex separator to $O(\sqrt{\log n})$.

Is there an $O(\log \mathsf{opt})$ approximation algorithm for directed balanced vertex separator, where $\mathsf{opt}$ is the optimal size of the directed balanced vertex separator ?

I would appreciate any references/pointers.

$\endgroup$

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.