User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Semidefinite programs and association schemes

Primary tabs

download
  • Open access
  • PDF
  • 176.07 K
Goemans, Michel X. Rendl, Franz

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

Document type Document de travail (Working Paper)
Access type Accès libre
Publication date 1999
Collection CORE Discussion Papers - 1999/62
Affiliation UCL - CORE - Center for Operations Research and Econometrics
Keywords Semidefinite programming ; Association scheme ; Maximum cut problem
Links
Bibliographic reference Goemans, Michel X. ; Rendl, Franz. Semidefinite programs and association schemes. CORE Discussion Papers ; 1999/62 (1999)
Permanent URL http://hdl.handle.net/2078.1/4074