Semidefinite Programs and Association Schemes

摘要

We consider semidefinite programs, where the matrices defining the problemall arise from some association scheme. We show that in this case the semidefinite program can be solved through an ordinary linearprogram. As an application, we consider the max-cut problem, where the underlying graph arises from an association scheme.