approximation for np hard graph problems

[Nick Mancuso]

Hello all,

Several months back I began a library built on top of networkx for approximation algorithms of np-hard graph/network problems (here). After rethinking the goals of the project, I felt it might make more sense to just be integrated to NetworkX where it may be of more use/make more of an impact. I realize there are no approximation algorithms implemented in NetworkX currently, and was curious if this is something that the developers feel would add value/use. Perhaps another submodule may be added (similar to bipartite)? The only problem is how to categorize them. Should there only be one approximation algorithm per optimization problem (best in terms of runtime? approximation ratio?)? Or should it be capable of having several algorithms (Christofide's 3/2 for TSP as well as a newer method)? 

What do you think?

[Aric Hagberg]

Hi Nick,

I like the idea of including approximation algorithms. Your code
looks really good - documentation and tests!. So if you are
willing to contribute that to NetworkX it would be a nice addition.
Please go ahead and open a ticket, or tickets, on the developer site
to propose what you would like to add.

I'm not sure right now how to categorize approximation algorithms, but
to some degree it doesn't matter that much. We can discuss that
further over on the NetworkX developer site.

Aric
--
Aric Hagberg
Los Alamos National Laboratory
math.lanl.gov/~hagberg