The matching problem has no small symmetric SDP

DOI10.1137/1.9781611974331.CH75MaRDI QIDQ4575655zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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)