The matching problem has no small symmetric SDP

DOI10.1007/s10107-016-1098-zzbMath1373.90094arXiv1504.00703MaRDI QIDQ1675264

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

Publication date: 27 October 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.00703

zbMATH Keywords

semidefinite programming; matching problem; extended formulations; TSP problem

Mathematics Subject Classification ID

90C22: Semidefinite programming

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)