http://openproblemgarden.org/op/approximation_ratio_for_maximum_edge_disjoint_paths_problem Comments for "Approximation Ratio for Maximum Edge Disjoint Paths problem" en http://openproblemgarden.org/op/approximation_ratio_for_maximum_edge_disjoint_paths_problem <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/bentz_cedric">Bentz</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Can the approximation ratio <img class="teximage" src="/files/tex/f1253d4c08d28b4696a2d2970370ca3ff8009cf2.png" alt="$ O(\sqrt{n}) $" /> be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than <img class="teximage" src="/files/tex/192453ccba701cc835624b0ec02d0a48c6a36e73.png" alt="$ \mathcal{APX} $" />-hardness? </div> </tr></td> </table> </td> </tr> </table> Bentz, Cedric approximation algorithms Disjoint paths planar graph polynomial algorithm Graph Theory http://openproblemgarden.org/op/approximation_ratio_for_maximum_edge_disjoint_paths_problem#comment Sun, 18 Apr 2010 00:43:42 +0200 jcmeyer 37211 at http://openproblemgarden.org