-2
$\begingroup$

How well can directed multicut be approximated in general graphs? and if it's worse than the (logn)^2 of G. Even etal in 1998 why the method in Even etal does not work for directed multicuts

I'm a bit confused that the $\sqrt{n}$ given in Approximation Algorithm for Directed Multicuts Yana Kortsarts etal 2004 and Anupam Gupta, Improved approximation algorithm for directed multicut In SODA 2003 are published later

To address Neal Youngs comment, I am asking about the (logn)^2 approximation algorithm for directed multicut given in section 3 of Even etal [1998] when they reduce subset fvs to directed multicut They seem to say circular networks only however I don't see why their argument doesn't work in general graphs

Sorry if this is easily found

$\endgroup$
  • $\begingroup$ What is your question? "I don't see why..." is not really a question. If you mean to ask why that algorithm doesn't work for directed multicut, you might have more luck if you add some details, such as how the problems that are addressed in each paper are defined, and what the relevant results in each paper are. $\endgroup$ – Neal Young Sep 16 at 12:25
  • $\begingroup$ @NealYoung It's 1) how well can directed multicut be approximated and 2) if it's worse than logn loglogn why the method in Even etal does not work for directed multicuts $\endgroup$ – user122938 Sep 16 at 14:46
  • $\begingroup$ @NealYoung I've clarified my question sorry if it's very elementary I'm still getting the hang of doing literature review would you consider reopening the question? $\endgroup$ – user122938 Sep 19 at 20:55
  • 1
    $\begingroup$ You'll need to at least improve the post if you want it to be considered for reopening, I think. You could edit it to clearly quote all the relevant problem definitions and theorems from the papers you mention, and explain more clearly why it seems to you that those more recent results are superseded by the older result. $\endgroup$ – Neal Young Sep 19 at 21:28
  • $\begingroup$ @NealYoung I've clarified that I am asking about the (logn)^2 approximation algorithm for directed multicut in circular networks given in section 3 of [Even et al 1998] and I'm not sure why it doesn't work from graphs in general $\endgroup$ – user122938 Sep 24 at 19:03