How well do local algorithms solve semidefinite programs?
From MaRDI portal
Publication:4978006
DOI10.1145/3055399.3055451zbMath1369.90118arXiv1610.05350OpenAlexW2539337210MaRDI QIDQ4978006
No author found.
Publication date: 17 August 2017
Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.05350
Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (5)
Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree ⋮ Suboptimality of local algorithms for a class of max-cut problems ⋮ Convex relaxation methods for community detection ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ On the computational tractability of statistical estimation on amenable graphs
This page was built for publication: How well do local algorithms solve semidefinite programs?
