### 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 and by Alon and Sudakov. 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. We also obtain similar results for several related problems. Our approach is quite general and could possibly be applied to some additional problems and algorithms.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 92-100 |

Number of pages | 9 |

State | Published - Dec 1 2001 |

Externally published | Yes |

Event | 2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States Duration: Apr 30 2001 → May 1 2001 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 2001 Operating Section Proceedings, American Gas Association |
---|---|

Country | United States |

City | Dallas, TX |

Period | 4/30/01 → 5/1/01 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

### Keywords

- Algorithms
- Performance
- Theory
- Verification

## 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

*Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 92-100). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).