The matching problem has no small symmetric SDP

DOI10.1137/1.9781611974331.CH75zbMATH Open1423.90209OpenAlexW2950943407MaRDI QIDQ4575655FDOQ4575655

Authors: Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch75

Recommendations

• The matching problem has no small symmetric SDP
• On the Power of Symmetric Linear Programs
• Expressing combinatorial optimization problems by linear programs
• Lower bounds on the size of semidefinite programming relaxations

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Semidefinite programming (90C22)

Cited In (7)

• Sum-of-squares rank upper bounds for matching problems
• Sum-of-squares rank upper bounds for matching problems
• The matching problem has no small symmetric SDP
• Symmetry matters for the sizes of extended formulations
• On the power of symmetric linear programs
• On the Power of Symmetric Linear Programs
• Affine reductions for LPs and SDPs

This page was built for publication: The matching problem has no small symmetric SDP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575655)