3 ms·
Theorists Draw Closer to Perfect Coloring
- lumpypua 11y agoAwesome article, thank you for posting. It's cool to see what's bleeding edge in math explained in such an approachable way.
- mcherm 11y agoIt is rare -- nearly unheard of -- that an active area of mathematical research would be simple enough to explain to a bright 9-yr-old. But this probably is. (Concepts: graph, coloring, max colors needed, clique... that's about it.) I think I'll try it with my kids.
- cschmidt 11y agoYou'll probably be interested in this guy, who does graph coloring problems for 7 year old kids. He even has coloring books: http://jdh.hamkins.org/math-for-seven-year-olds-graph-coloring-chromatic-numbers-eulerian-paths/ http://jdh.hamkins.org/math-for-seven-year-olds-graph-colori...
- danbruc 11y agoIf 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. it suffers from numerical instability. So this is probably about the search for a practical algorithm. [1] http://www.zib.eu/groetschel/pubnew/paper/groetschellovaszschrijver1984b.pdf http://www.zib.eu/groetschel/pubnew/paper/groetschellovaszsc...
- shoo 11y agoIf 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 agoThat 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
- spdustin 11y agoThe little interactive in the article is practically begging to be made into a game.