3 ms·

If I understand it correctly a polynomial time algorithm for coloring perfect graphs has been found in 1984 [1] but the algorithm is no good in practice, i.e. i

• shoo 11y ago
  If possible, could you please go into a bit more detail regarding numerical instability? Is the instability a general hazard with the ellipsoid method, or particular to to the Gr\"{o}tschel et al algorithms? I've heard of the odd occasion where there is a common belief that an old algorithm does not perform well in practice, based on older experimental studies, but it turns out that the algorithm is actually quite effective, but perhaps only when combined with a few other good implementation decisions.
  • danbruc 11y ago
    That is far beyond my knowledge of graph theory and convex optimization but the Wikipedia article [1] suggests that is a general problem of the method and it only works well for low dimensional data. [1] https://en.wikipedia.org/wiki/Ellipsoid_method#Performance https://en.wikipedia.org/wiki/Ellipsoid_method#Performance