missing algorithms

[CarloLucibello]

Here is a partial list of missing algorithms. For hard problems (as most problems in this list) both exact and heuristic solvers should be implemented.

Problems not yet addressed in Erdos

• [ ] coloring for fixed q
• [ ] coloring number and optimal coloring
• [ ] maximum independent set (also known as vertex packing problem)
• [ ] maximum weight independent set (weights on vertices)
• [ ] minimum vertex cover
• [ ] graph isomorphism
  • [ ] fastest known exact algorithm is Algorithm 4 here https://arxiv.org/pdf/1607.00547.pdf
• [ ] prize collecting steiner tree
  • [ ] message passing heuristic https://arxiv.org/abs/1309.0346
• [ ] travelling salesman problem
• [ ] clique problems
• [ ] maximum weight b-matching
  • [ ] efficient exact solver (Edmond's)
  • [ ] linear programming as bootstrap for interger programming
  • [ ] message passing heuristic http://www.jmlr.org/proceedings/papers/v15/huang11a/huang11a.pdf

New algorithms for "old" problems

• [ ] Community Detection
  • [ ] SCoDA https://arxiv.org/pdf/1703.02955.pdf
• [ ] Matching
  • [ ] Hungarian Algorithm https://github.com/Gnimuc/Hungarian.jl

Most problems can be formulated as integer programming problems and solved (at least for small instances) through JuMP and generict IP solver.

Simulated Annealing could be implemented as a general heuristic solver. See also https://github.com/carlobaldassi/RRRMC.jl.

For most problems message passing heuristics (belief propagation) can be found in the literature