coherent configurations

Relaxations of combinatorial problems via association schemes

  • Etienne de Klerk
  • Fernando Mário de Oliveira Filho
  • Dmitrii V. Pasechnik
    • Categories Combinatorial Optimization, Semi-definite Programming Tags ,

    In this chapter we study a class of semidefinite programming relaxations of combinatorial problems. These relaxations are derived using the theory of coherent configurations in algebraic combinatorics. CitationDraft version of a chapter for “Handbook on SDP II” (M. Anjos and J. Lasserre, eds.), Springer.ArticleDownload View PDF

    On semidefinite programming relaxations of maximum k-section

  • Etienne de Klerk
  • Cristian Dobre
  • Renata Sotirov
  • Dmitrii V. Pasechnik
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We derive a new semidefinite programming bound for the maximum k-section problem. For k=2 (i.e. for maximum bisection), the new bound is least as strong as the well-known bound by Frieze and Jerrum [A. Frieze and M. Jerrum. Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1): 67-81, 1997]. For k > 2 … Read more