### Abstract

Semidefinite programs (SDP) have been used in many recentapproximation algorithms. We develop a general primal-dualapproach to solve SDPs using a generalization ofthe well-known multiplicative weights update rule to symmetricmatrices. For a number of problems, such as Sparsest Cut and Balanced Separator in undirected and directed weighted graphs, and the Min UnCut problem, this yields combinatorial approximationalgorithms that are significantly more efficient than interiorpoint methods. The design of our primal-dual algorithms is guidedby a robust analysis of rounding algorithms used to obtain integersolutions from fractional ones.

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

Title of host publication | STOC'07 |

Subtitle of host publication | Proceedings of the 39th Annual ACM Symposium on Theory of Computing |

Pages | 227-236 |

Number of pages | 10 |

DOIs | |

State | Published - Oct 30 2007 |

Event | STOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 11 2007 → Jun 13 2007 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | STOC'07: 39th Annual ACM Symposium on Theory of Computing |
---|---|

Country | United States |

City | San Diego, CA |

Period | 6/11/07 → 6/13/07 |

### All Science Journal Classification (ASJC) codes

- Software

## Fingerprint Dive into the research topics of 'A combinatorial, primal-dual approach to semidefinite programs'. Together they form a unique fingerprint.

## Cite this

*STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing*(pp. 227-236). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1250790.1250823