It seems that Goemans and Williamson give a unique representation for each graph of the semidefinite relaxation (elements $y_{ij}$ of Y). However, semidefinite programming may give the same maximum value of the objective function for different matrices Y, if I am correct. This means that you may get up to more than one unique representation in n dimensions of a graph. Can somebody tell me if this is correct please?

PS: the Cholesky decomposition we do, gives a unique set of n vectors after finding Y, however I believe that Y is not necessarily unique, so you may get many different sets of vectors $v_{ij}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.