Top

Journal of Combinatorial Optimization

Published in:

06-09-2017

Sum-of-squares rank upper bounds for matching problems

Authors: Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli

Published in: Journal of Combinatorial Optimization | Issue 3/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The matching problem is one of the most studied combinatorial optimization problems in the context of extended formulations and convex relaxations. In this paper we provide upper bounds for the rank of the sum-of-squares/Lasserre hierarchy for a family of matching problems. In particular, we show that when the problem formulation is strengthened by incorporating the objective function in the constraints, the hierarchy requires at most \(\left\lceil \frac{k}{2} \right\rceil \) levels to refute the existence of a perfect matching in an odd clique of size \(2k+1\).

previous article Uniqueness of equilibria in atomic splittable polymatroid congestion games

next article Robust trading mechanisms over 0/1 polytopes

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

An r-uniform hypergraph is given by a set of vertices V and set of hyperedges E where each hyperedge \(e \in E\) is incident to exactly r vertices.

The appendix of Barak et al. (2014) is not available in the version published in the conference proceedings. The statement and proof can be found in Corollary A.3 in the arxiv version at https://arxiv.org/pdf/1312.6652.pdf.

Au Y, Tunçel L (2011) Complexity analyses of Bienstock–Zuckerberg and Lasserre relaxations on the matching and stable set polytopes. In: IPCO, pp 14–26

Au Y, Tunçel L (2013) A comprehensive analysis of polyhedral lift-and-project methods. CoRR. arXiv:1312.5972

Avis D, Bremner D, Tiwary HR, Watanabe O (2014) Polynomial size linear programs for non-bipartite matching problems and other problems in P. CoRR abs/1408.0807. arXiv:1408.0807

Barak B, Kelner JA, Steurer D (2014) Rounding sum-of-squares relaxations. In: STOC, pp 31–40. doi:10.1145/2591796.2591886

Braun G, Brown-Cohen J, Huq A, Pokutta S, Raghavendra P, Roy A, Weitz B, Zink D (2016) The matching problem has no small symmetric SDP. In: SODA, pp 1067–1078. doi:10.1137/1.9781611974331.ch75

Chan SO, Lee JR, Raghavendra P, Steurer D (2013) Approximate constraint satisfaction requires large LP relaxations. In: FOCS. IEEE Computer Society, pp 350–359. doi:10.1109/FOCS.2013.45

Edmonds J (1965) Paths, trees and flowers. Can J Math 17:449–467MathSciNetCrossRefMATH

Fawzi H, Saunderson J, Parrilo PA (2016) Sparse sums of squares on finite Abelian groups and improved semidefinite lifts. Math Program. doi:10.1007/s10107-015-0977-z MathSciNetMATH

Goemans MX, Tunçel L (2001) When does the positive semidefiniteness constraint help in lifting procedures? Math Oper Res 26(4):796–815. doi:10.1287/moor.26.4.796.10012 MathSciNetCrossRefMATH

Grigoriev D (2001) Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theor Comput Sci 259(1–2):613–622MathSciNetCrossRefMATH

Horn RA, Johnson CR (2013) Matrix analysis. Cambridge University Press, CambridgeMATH

Karlin AR, Mathieu C, Nguyen CT (2011) Integrality gaps of linear and semi-definite programming relaxations for Knapsack. In: IPCO, pp 301–314

Kurpisz A, Leppänen S, Mastrolilli M (2015) On the hardest problem formulations for the 0/1 Lasserre hierarchy. In: Automata, languages, and programming—42nd international colloquium, ICALP 2015. Proceedings, part I, pp 872–885

Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J Optim 11(3):796–817MathSciNetCrossRefMATH

Laurent M (2003) A comparison of the Sherali–Adams, Lovász–Schrijver, and Lasserre relaxations for 0–1 programming. Math Oper Res 28(3):470–496MathSciNetCrossRefMATH

Lee JR, Raghavendra P, Steurer D (2015) Lower bounds on the size of semidefinite programming relaxations. In: Servedio RA, Rubinfeld R (eds) STOC. ACM, pp 567–576. doi:10.1145/2746539.2746599

Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0–1 optimization. SIAM J Optim 1(12):166–190MathSciNetCrossRefMATH

Mathieu C, Sinclair A (2009) Sherali–Adams relaxations of the matching polytope. In: STOC, pp 293–302. doi:10.1145/1536414.1536456

Nesterov Y (2000) Global quadratic optimization via conic relaxation. Kluwer Academic Publishers, Dordrecht, pp 363–384

O’Donnell R, Zhou Y (2013) Approximability and proof complexity. In: SODA, pp 1537–1556

Parrilo P (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. Thesis, California Institute of Technology

Rothvoß T (2013) The Lasserre hierarchy in approximation algorithms. In: Lecture Notes for the MAPSP 2013—Tutorial

Rothvoß T (2014) The matching polytope has exponential extension complexity. In: STOC, pp 263–272. doi:10.1145/2591796.2591834

Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J Discrete Math 3(3):411–430MathSciNetCrossRefMATH

Shor N (1987) Class of global minimum bounds of polynomial functions. Cybernetics 23(6):731–734CrossRefMATH

Stephen T, Tunçel L (1999) On a representation of the matching polytope via semidefinite liftings. Math Oper Res 24(1):1–7MathSciNetCrossRefMATH

Worah P (2015) Rank bounds for a hierarchy of Lovász and Schrijver. J Comb Optim 30(3):689–709. doi:10.1007/s10878-013-9662-4 MathSciNetCrossRefMATH

Yannakakis M (1991) Expressing combinatorial optimization problems by linear programs. J Comput Syst Sci 43(3):441–466. doi:10.1016/0022-0000(91)90024-Y MathSciNetCrossRefMATH

Title: Sum-of-squares rank upper bounds for matching problems
Authors: Adam Kurpisz
Samuli Leppänen
Monaldo Mastrolilli
Publication date: 06-09-2017
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2018
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-017-0169-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2018

Optimization problems with color-induced budget constraints

Subset sum problems with digraph constraints

The QAP-polytope and the graph isomorphism problem

An algorithm for finding a representation of a subtree distance

Lot sizing with storage losses under demand uncertainty

Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays

Premium Partner