×

zbMATH — the first resource for mathematics

The matching problem has no small symmetric SDP. (English) Zbl 1373.90094
Summary: M. Yannakakis [J. Comput. Syst. Sci. 43, No. 3, 441–466 (1991; Zbl 0748.90074)] showed that the matching problem does not have a small symmetric linear program. T. Rothvoss [in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14. New York, NY: Association for Computing Machinery (ACM). 263–272 (2014; Zbl 1315.90038)] recently proved that any, not necessarily symmetric, linear program also has exponential size. In light of this, it is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an \(O\)(\(k\))-round Lasserre SDP relaxation for the asymmetric metric traveling salesperson problem yields at least as good an approximation as any symmetric SDP relaxation of size \(n^{k}\). The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours.

MSC:
90C22 Semidefinite programming
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor \(2 - ε \). In: Proceedings of the FOCS, pp. 1123-1142 (2015). doi:10.1109/FOCS.2015.73 · Zbl 1310.90100
[2] Braun, G., Pokutta, S.: An algebraic approach to symmetric extended formulations. In: Proceedings of the ISCO, pp. 141-152. Springer, Heidelberg, ISBN 978-3-642-32147-4 (2012). doi:10.1007/978-3-642-32147-4_14 · Zbl 1370.90292
[3] Braun, G., Pokutta, S.: The matching polytope does not admit fully-polynomial size relaxation schemes. In: Proceedings of the SODA, pp. 837-846 (2015a). doi:10.1137/1.9781611973730.57 · Zbl 1372.68251
[4] Braun, G; Pokutta, S, The matching problem has no fully polynomial size linear programming relaxation schemes, IEEE Trans. Inf. Theory, 61, 5754-5764, (2015) · Zbl 1359.68300
[5] Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). In: Proceedings of the FOCS, pp. 480-489 (2012) · Zbl 1343.68308
[6] Braun, G; Fiorini, S; Pokutta, S; Steurer, D, Approximation limits of linear programs (beyond hierarchies), Math. Oper. Res., 40, 756-772, (2015) · Zbl 1343.68308
[7] Braun, G., Pokutta, S., Zink, D.: Inapproximability of combinatorial problems via small LPs and SDPs. In: Proceedings of the STOC, pp. 107-116 (2015b). doi:10.1145/2746539.2746550 · Zbl 1321.90098
[8] Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of the STOC, pp. 161-170. ACM, ISBN 978-1-4503-2029-0 (2013). doi:10.1145/2488608.2488629 · Zbl 1293.68137
[9] Briët, J., Dadush, D., Pokutta, S.: On the existence of 0/1 polytopes with high semidefinite extension complexity. In: Proceedings of the ESA, pp. 217-228. Springer, Berlin (2013) · Zbl 1395.90241
[10] Briët, J; Dadush, D; Pokutta, S, On the existence of 0/1 polytopes with high semidefinite extension complexity, Math. Program., 153, 179-199, (2015) · Zbl 1325.90066
[11] Buss, S., Grigoriev, D., Impagliazzo, R., Pitassi, T.: Linear gaps between degrees for the polynomial calculus modulo distinct primes. In: Proceedings of the STOC, pp. 547-556 (1999) · Zbl 1345.03105
[12] Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: Proceedings of the FOCS, pp. 350-359 (2013) · Zbl 1394.68170
[13] Dixon, J.D., Mortimer, B.: Permutation Groups. Springer, Berlin (1996) · Zbl 0951.20001
[14] Edmonds, J, Maximum matching and a polyhedron with \(0,1\)-vertices, J. Res. Nat. Bur. Stand. Sect. B, 69B, 125-130, (1965) · Zbl 0141.21802
[15] Fiorini, S., Massar, S., Pokutta, S., Tiwary, H. R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of the STOC, pp. 95-106 (2012) · Zbl 1286.90125
[16] Fiorini, S; Massar, S; Pokutta, S; Tiwary, HR; de Wolf, R, Exponential lower bounds for polytopes in combinatorial optimization, J. Assoc. Comput. Mach., 62, 17, (2015) · Zbl 1333.90107
[17] Goemans, MX, Smallest compact formulation for the permutahedron, Math. Program., 153, 5-11, (2015) · Zbl 1322.90048
[18] Goemans, MX; Williamson, DP, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach., 42, 1115-1145, (1995) · Zbl 0885.68088
[19] Gouveia, J; Parrilo, PA; Thomas, RR, Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 248-264, (2011) · Zbl 1291.90172
[20] Grigoriev, D, Linear lower bound on degrees of positivstellensatz calculus proofs for the parity, Theor. Comput. Sci., 259, 613-622, (2001) · Zbl 0974.68192
[21] Kaibel, V., Pashkovich, K., Theis, D.O.: Symmetry matters for the sizes of extended formulations. In: Proceedings of the IPCO, pp. 135-148 (2010). doi:10.1007/978-3-642-13036-6_11 · Zbl 1285.90052
[22] Lee, J.R., Raghavendra, P., Steurer, D., Tan, N.: On the power of symmetric LP and SDP relaxations. In: Proceedings of the CCC, pp. 13-21 (2014)
[23] Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: Proceedings of the STOC, pp. 567-576 (2015). doi:10.1145/2746539.2746599 · Zbl 1321.90099
[24] Pashkovich, K, Tight lower bounds on the sizes of symmetric extensions of permutahedra and similar results, Math. Oper. Res., 39, 1330-1339, (2014) · Zbl 1310.90100
[25] Rothvoß, T.: The matching polytope has exponential extension complexity. In: Proceedings of the STOC, pp. 263-272 (2014) · Zbl 1315.90038
[26] Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 411-430, (1990) · Zbl 0712.90050
[27] Vandenberghe, L; Boyd, S, Semidefinite programming, SIAM Rev., 38, 49-95, (1996) · Zbl 0845.65023
[28] Yannakakis, M.: Expressing combinatorial optimization problems by linear programs (extended abstract). In: Proceedings of the STOC, pp. 223-228 (1988) · Zbl 0748.90074
[29] Yannakakis, M, Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci., 43, 441-466, (1991) · Zbl 0748.90074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.