Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms

DOI10.1137/S0895480100379713zbMath0992.68237OpenAlexW2022589731MaRDI QIDQ2784501

Noga Alon, Uri Zwick, Benjamin Sudakov

Publication date: 23 April 2002

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480100379713

zbMATH Keywords

semidefinite programmingapproximation algorithmMAX CUT

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation ⋮ On the eigenvalues of Grassmann graphs, bilinear forms graphs and Hermitian forms graphs

This page was built for publication: Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms