Inference on graphs via semidefinite programming
Inference problems on graphs arise naturally when trying to make sense of network data. Oftentimes, these problems are formulated as intractable optimization programs. This renders the need for fast heuristics to find adequate solutions and for the study of their performance. For a certain class of...
Main Author: | |
---|---|
Other Authors: | |
Format: | Article |
Language: | en_US |
Published: |
National Academy of Sciences (U.S.)
2017
|
Online Access: | http://hdl.handle.net/1721.1/109985 https://orcid.org/0000-0002-7331-7557 |
_version_ | 1826216078421786624 |
---|---|
author | Sousa Bandeira, Afonso Jose |
author2 | Massachusetts Institute of Technology. Department of Mathematics |
author_facet | Massachusetts Institute of Technology. Department of Mathematics Sousa Bandeira, Afonso Jose |
author_sort | Sousa Bandeira, Afonso Jose |
collection | MIT |
description | Inference problems on graphs arise naturally when trying to make sense of network data. Oftentimes, these problems are formulated as intractable optimization programs. This renders the need for fast heuristics to find adequate solutions and for the study of their performance. For a certain class of problems, Javanmard et al. (1) successfully use tools from statistical physics to analyze the performance of semidefinite programming relaxations, an important heuristic for intractable problems. |
first_indexed | 2024-09-23T16:41:58Z |
format | Article |
id | mit-1721.1/109985 |
institution | Massachusetts Institute of Technology |
language | en_US |
last_indexed | 2024-09-23T16:41:58Z |
publishDate | 2017 |
publisher | National Academy of Sciences (U.S.) |
record_format | dspace |
spelling | mit-1721.1/1099852022-10-03T07:41:36Z Inference on graphs via semidefinite programming Sousa Bandeira, Afonso Jose Massachusetts Institute of Technology. Department of Mathematics Sousa Bandeira, Afonso Jose Inference problems on graphs arise naturally when trying to make sense of network data. Oftentimes, these problems are formulated as intractable optimization programs. This renders the need for fast heuristics to find adequate solutions and for the study of their performance. For a certain class of problems, Javanmard et al. (1) successfully use tools from statistical physics to analyze the performance of semidefinite programming relaxations, an important heuristic for intractable problems. National Science Foundation (U.S.) (Grant DMS- 1317308) 2017-06-16T20:14:55Z 2017-06-16T20:14:55Z 2016-04 Article http://purl.org/eprint/type/JournalArticle 0027-8424 1091-6490 http://hdl.handle.net/1721.1/109985 Bandeira, Afonso S. “Inference on Graphs via Semidefinite Programming.” Proceedings of the National Academy of Sciences 113, no. 16 (April 8, 2016): 4238–4239. © 2017 National Academy of Sciences https://orcid.org/0000-0002-7331-7557 en_US http://dx.doi.org/10.1073/pnas.1603405113 Proceedings of the National Academy of Sciences of the United States of America Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf National Academy of Sciences (U.S.) PNAS |
spellingShingle | Sousa Bandeira, Afonso Jose Inference on graphs via semidefinite programming |
title | Inference on graphs via semidefinite programming |
title_full | Inference on graphs via semidefinite programming |
title_fullStr | Inference on graphs via semidefinite programming |
title_full_unstemmed | Inference on graphs via semidefinite programming |
title_short | Inference on graphs via semidefinite programming |
title_sort | inference on graphs via semidefinite programming |
url | http://hdl.handle.net/1721.1/109985 https://orcid.org/0000-0002-7331-7557 |
work_keys_str_mv | AT sousabandeiraafonsojose inferenceongraphsviasemidefiniteprogramming |