Superior approximation algorithm for finding Maximum (or large) Cliques in very large graphs. (Multi-Partite Graphs can be found)

Our maximum clique finding algorithm (that is polynomial in its run time) and which seems (from DIMACS benchmark tests) to run better than other methods that are presently available would be beneficial to IBM because it would allow you to solve complex optimization problems more efficiently. The maximum clique problem is an NP-complete problem that is difficult to solve for large graphs. A polynomial-time algorithm (that is sometimes….but maybe not always optimal) for solving the maximum clique problem would significantly reduce the computational time required to solve this problem and other related problems.  Our solutions tested on the DIMACS benchmarks with our MVP have come in at 80-100% accuracy (if the optimal-clique is 100, we find cliques of size 80-100), but we can turn up the accuracy as much as needed...if we slow down the speed.  (We need to add in an IF THEN method for Multi-Partite graphs, but the strategy is quite sound and will find them, even if deeply hidden within the structure.  It's pretty cool.

IBM has developed many products that can be used to solve the maximum clique problem, including IBM ILOG CPLEX Optimization Studio and IBM SPSS Modeler. These products are used in various fields such as finance, healthcare, and transportation to solve complex optimization problems. A better maximum clique algorithm would allow these products to solve larger and more complex optimization problems more efficiently, which would be beneficial for IBM and its customers.