Dealing with inequality constraints in large scale semidefinite relaxations for graph coloring and maximum clique problems

Semidefinite programs (SDPs) can be solved in polynomial time by interior point methods. However, when the dimension of the problem gets large, interior point methods become impractical both in terms of computational time and memory requirements. First order methods, such as Alternating Direction Methods of Multipliers (ADMMs), turned out to be suitable algorithms to deal … Read more