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

Full description

Bibliographic Details
Main Author: Sousa Bandeira, Afonso Jose
Other Authors: Massachusetts Institute of Technology. Department of Mathematics
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