Constructing worst case instances for semidefinite programming based approximation algorithms

Noga Alon, Benny Sudakov, Uri Zwick

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

Semidefinite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees using local ratio techniques. Are the bounds obtained in this way tight? This problem was considered before by Karloff [SIAM J. Comput., 29 (1999), pp. 336-350] and by Alon and Sudakov [Combin. Probab. Comput., 9 (2000), pp. 1-12]. Here we further extend their results and show, for the first time, that the local analyses of the Goemans and Williamson MAX CUT algorithm, as well as its extension by Zwick, are tight for every possible relative size of the maximum cut in the sense that the expected value of the solutions obtained by the algorithms may be as small as the analyses ensure. We also obtain similar results for a related problem. Our approach is quite general and could possibly be applied to some additional problems and algorithms.

Original languageEnglish (US)
Pages (from-to)58-72
Number of pages15
JournalSIAM Journal on Discrete Mathematics
Volume15
Issue number1
DOIs
StatePublished - Oct 1 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Approximation algorithm
  • MAX CUT
  • Semidefinite programming

Fingerprint Dive into the research topics of 'Constructing worst case instances for semidefinite programming based approximation algorithms'. Together they form a unique fingerprint.

Cite this