### Abstract

We construct integrality gap instances for SDP relaxation of the MAXIMUM CUT and the SPARSEST CUT problems. If the triangle inequality constraints are added to the SDP, then the SDP vectors naturally define an n-point negative type metric where n is the number of vertices in the problem instance. Our gap-instances satisfy a stronger constraint that every sub-metric on t = O((log log log n)1/6) points is isometrically embeddable into ℓ_{1}. The local ℓ_{1}-embeddability constraints are implied when the basic SDP relaxation is augmented with t rounds of the Sherali-Adams LP-relaxation. For the MAXIMUM CUT problem, we obtain an optimal gap of α_{GW} ^{-1} - ε, where αGW is the Goemans-Williamson constant [11] and ε > 0 is an arbitrarily small constant. For the SPARSEST C UT problem, we obtain a gap of Ω((log log log n) 1/13). The latter result can be rephrased as a construction of an n-point negative type metric such that every t-point sub-metric is isometrically ℓ_{1} -embeddable, but embedding the whole metric into ℓ_{1} incurs distortion Ω((log log log n) 1/13).

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

Title of host publication | Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 |

Pages | 565-574 |

Number of pages | 10 |

DOIs | |

State | Published - 2009 |

Event | 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 - Atlanta, GA, United States Duration: Oct 25 2009 → Oct 27 2009 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 |
---|---|

Country | United States |

City | Atlanta, GA |

Period | 10/25/09 → 10/27/09 |

### ASJC Scopus subject areas

- Computer Science(all)

## Cite this

_{1}-embeddability. In

*Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009*(pp. 565-574). [5438596] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2009.37