Rounding sum-of-squares relaxations
We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a combining algorithm---an algorithm tha...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/93083 https://orcid.org/0000-0002-4257-4198 |
| _version_ | 1826217598661951488 |
|---|---|
| author | Barak, Boaz Kelner, Jonathan Adam Steurer, David |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Barak, Boaz Kelner, Jonathan Adam Steurer, David |
| author_sort | Barak, Boaz |
| collection | MIT |
| description | We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a combining algorithm---an algorithm that maps a distribution over solutions into a (possibly weaker) solution---into a rounding algorithm that maps a solution of the relaxation to a solution of the original problem. |
| first_indexed | 2024-09-23T17:06:14Z |
| format | Article |
| id | mit-1721.1/93083 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:06:14Z |
| publishDate | 2015 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/930832022-10-03T10:24:46Z Rounding sum-of-squares relaxations Barak, Boaz Kelner, Jonathan Adam Steurer, David Massachusetts Institute of Technology. Department of Mathematics Kelner, Jonathan Adam We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a combining algorithm---an algorithm that maps a distribution over solutions into a (possibly weaker) solution---into a rounding algorithm that maps a solution of the relaxation to a solution of the original problem. 2015-01-20T20:44:21Z 2015-01-20T20:44:21Z 2014-05 Article http://purl.org/eprint/type/JournalArticle 978-1-4503-2710-7 http://hdl.handle.net/1721.1/93083 Boaz Barak, Jonathan A. Kelner, and David Steurer. 2014. Rounding sum-of-squares relaxations. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14). ACM, New York, NY, USA, 31-40. https://orcid.org/0000-0002-4257-4198 en_US http://dx.doi.org/10.1145/2591796.2591886 Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Barak, Boaz Kelner, Jonathan Adam Steurer, David Rounding sum-of-squares relaxations |
| title | Rounding sum-of-squares relaxations |
| title_full | Rounding sum-of-squares relaxations |
| title_fullStr | Rounding sum-of-squares relaxations |
| title_full_unstemmed | Rounding sum-of-squares relaxations |
| title_short | Rounding sum-of-squares relaxations |
| title_sort | rounding sum of squares relaxations |
| url | http://hdl.handle.net/1721.1/93083 https://orcid.org/0000-0002-4257-4198 |
| work_keys_str_mv | AT barakboaz roundingsumofsquaresrelaxations AT kelnerjonathanadam roundingsumofsquaresrelaxations AT steurerdavid roundingsumofsquaresrelaxations |