×

Integrality gaps for colorful matchings. (English) Zbl 1506.90261

Summary: We study the integrality gap of the natural linear programming relaxation for the Bounded Color Matching (BCM) problem. We provide several families of instances and establish lower bounds on their integrality gaps and we study how the Sherali-Adams “lift-and-project” technique behaves on these instances. We complement these results by showing that if we exclude certain simple sub-structures from our input graphs, then the integrality gap of the natural linear formulation strictly improves. To prove this, we adapt for our purposes the results of Z. Fueredi [Combinatorica 1, 155–162 (1981; Zbl 0494.05045)]. We further leverage this to show upper bounds on the performance of the Sherali-Adams hierarchy when applied to the natural LP relaxation of the BCM problem.

MSC:

90C35 Programming involving graphs or networks
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90C10 Integer programming

Citations:

Zbl 0494.05045
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Papadimitriou, C. H.; Yannakakis, M., The complexity of restricted spanning tree problems, J. ACM, 29, 2, 285-309 (1982) · Zbl 0478.68068
[2] Mulmuley, K.; Vazirani, U. V.; Vazirani, V. V., Matching is as easy as matrix inversion, Combinatorica, 7, 1, 105-113 (1987) · Zbl 0632.68041
[3] Yuster, R., Almost exact matchings, Algorithmica, 63, 1-2, 39-50 (2012) · Zbl 1236.68107
[4] Karzanov, A. V., Maximum matching of given weight in complete and complete bipartite graphs, Cybernetics, 23, 1, 8-13 (1987) · Zbl 0688.05070
[5] Yi, T.; Murty, K. G.; Spera, C., Matchings in colored bipartite networks, Discrete Appl. Math., 121, 1-3, 261-277 (2002) · Zbl 1020.90041
[6] Stamoulis, G., Approximation Algorithms for Bounded Color Matchings via Convex Decompositions, (Csuhaj-Varjú, E.; Dietzfelbinger, M.; Ésik, Z., Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II. Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, Lecture Notes in Computer Science, vol. 8635 (2014), Springer), 625-636 · Zbl 1426.68308
[7] Parekh, O., Iterative packing for demand and hypergraph matching, (Günlük, O.; Woeginger, G. J., Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings. Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6655 (2011), Springer), 349-361 · Zbl 1341.90116
[8] Parekh, O.; Pritchard, D., Generalized hypergraph matching via iterated packing and local ratio, (Bampis, E.; Svensson, O., Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers. Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8952 (2014), Springer), 207-223 · Zbl 1457.68310
[9] Edmonds, J., Maximum matching and a polyhedron with \(0, 1\) vertices, J. Res. Nat. Bureau Standards, 69 B, 125-130 (1965) · Zbl 0141.21802
[10] Sherali, H. D.; Adams, W. P., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 3, 411-430 (1990) · Zbl 0712.90050
[11] Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166-190 (1991) · Zbl 0754.90039
[12] Balas, E.; Ceria, S.; Cornuéjols, G., A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. Program., 58, 295-324 (1993) · Zbl 0796.90041
[13] Lasserre, J. B., An explicit equivalent positive semidefinite program for nonlinear 0-1 programs, SIAM J. Optim., 12, 3, 756-769 (2002) · Zbl 1007.90046
[14] Bienstock, D.; Zuckerberg, M., Subset algebra lift operators for 0-1 integer programming, SIAM J. Optim., 15, 1, 63-95 (2004) · Zbl 1077.90041
[15] Laurent, M., A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming, Math. Oper. Res., 28, 3, 470-496 (2003) · Zbl 1082.90084
[16] Arora, S.; Bollobás, B.; Lovász, L.; Tourlakis, I., Proving integrality gaps without knowing the linear program, Theory Comput., 2, 1, 19-51 (2006) · Zbl 1213.68306
[17] Mathieu, C.; Sinclair, A., Sherali-Adams relaxations of the matching polytope, (Mitzenmacher, M., Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009 (2009), ACM), 293-302 · Zbl 1304.90144
[18] A.R. Karlin, C. Mathieu, C.T. Nguyen, Integrality gaps of linear and semi-definite programming relaxations for knapsack, in: IPCO, 2011, pp. 301-314.; A.R. Karlin, C. Mathieu, C.T. Nguyen, Integrality gaps of linear and semi-definite programming relaxations for knapsack, in: IPCO, 2011, pp. 301-314. · Zbl 1341.90112
[19] Chan, Y. H.; Lau, L. C., On linear and semidefinite programming relaxations for hypergraph matching, Math. Program., 135, 1-2, 123-148 (2012) · Zbl 1254.90107
[20] Cheriyan, J.; Gao, Z.; Georgiou, K.; Singla, S., On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy, Math. Program., 159, 1-2, 1-29 (2016) · Zbl 1346.90569
[21] Chlamtac, E.; Friggstad, Z.; Georgiou, K., Lift-and-project methods for set cover and knapsack, (Dehne, F.; Solis-Oba, R.; Sack, J., Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings. Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings, Lecture Notes in Computer Science, vol. l8037 (2013), Springer), 256-267 · Zbl 1391.68123
[22] A. Kurpisz, M. Mastrolilli, C. Mathieu, T. Mömke, V. Verdugo, A. Wiese, Semidefinite and linear programming integrality gaps for scheduling identical machines, in: Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, 2016, pp. 152-163.; A. Kurpisz, M. Mastrolilli, C. Mathieu, T. Mömke, V. Verdugo, A. Wiese, Semidefinite and linear programming integrality gaps for scheduling identical machines, in: Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, 2016, pp. 152-163. · Zbl 1402.90054
[23] E. Chlamtac, G. Singh, Improved approximation guarantees through higher levels of SDP hierarchies, in: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008, 2008, pp. 49-62.; E. Chlamtac, G. Singh, Improved approximation guarantees through higher levels of SDP hierarchies, in: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008, 2008, pp. 49-62. · Zbl 1159.68664
[24] Arora, S.; Chlamtac, E., New approximation guarantee for chromatic number, (Kleinberg, J. M., Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006 (2006), ACM), 215-224 · Zbl 1301.05324
[25] Y. Yoshida, Y. Zhou, Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems, in: Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014, 2014, pp. 423-438.; Y. Yoshida, Y. Zhou, Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems, in: Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014, 2014, pp. 423-438. · Zbl 1366.68369
[26] Manurangsi, P.; Raghavendra, P., A birthday repetition theorem and complexity of approximating dense CSPs, (Chatzigiannakis, I.; Indyk, P.; Kuhn, F.; Muscholl, A., 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland. 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, LIPIcs, vol. 80 (2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 78:1-78:15 · Zbl 1441.68048
[27] M. Bateni, M. Charikar, V. Guruswami, MaxMin allocation via degree lower-bounded arborescences, in: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, 2009. pp. 543-552.; M. Bateni, M. Charikar, V. Guruswami, MaxMin allocation via degree lower-bounded arborescences, in: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, 2009. pp. 543-552. · Zbl 1304.91143
[28] N. Bansal, A. Srinivasan, O. Svensson, Lift-and-round to improve weighted completion time on unrelated machines, in: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, 2016, pp. 156-167.; N. Bansal, A. Srinivasan, O. Svensson, Lift-and-round to improve weighted completion time on unrelated machines, in: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, 2016, pp. 156-167. · Zbl 1373.68151
[29] A. Magen, M. Moharrami, Robust algorithms for on minor-free graphs based on the Sherali-Adams hierarchy, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, 2009, pp. 258-271.; A. Magen, M. Moharrami, Robust algorithms for on minor-free graphs based on the Sherali-Adams hierarchy, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, 2009, pp. 258-271. · Zbl 1255.68306
[30] W.F. de la Vega, C. Kenyon-Mathieu, Linear programming relaxations of maxcut, in: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, 2007, pp. 53-61.; W.F. de la Vega, C. Kenyon-Mathieu, Linear programming relaxations of maxcut, in: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, 2007, pp. 53-61. · Zbl 1302.90176
[31] E. Chlamtac, R. Krauthgamer, P. Raghavendra, Approximating sparsest cut in graphs of bounded treewidth, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010, Proceedings, 2010, pp. 124-137.; E. Chlamtac, R. Krauthgamer, P. Raghavendra, Approximating sparsest cut in graphs of bounded treewidth, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010, Proceedings, 2010, pp. 124-137. · Zbl 1304.68213
[32] Gupta, A.; Talwar, K.; Witmer, D., Sparsest cut on bounded treewidth graphs: algorithms and hardness results, (Boneh, D.; Roughgarden, T.; Feigenbaum, J., Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013 (2013), ACM), 281-290 · Zbl 1293.05042
[33] Füredi, Z., Maximum degree and fractional matchings in uniform hypergraphs, Combinatorica, 1, 2, 155-162 (1981) · Zbl 0494.05045
[34] Nomikos, C.; Pagourtzis, A.; Zachos, S., Randomized and approximation algorithms for blue-red matching, (Kucera, L.; Kucera, A., Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings. Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4708 (2007), Springer), 715-725 · Zbl 1147.68872
[35] Nomikos, C.; Pagourtzis, A.; Zachos, S., Minimizing request blocking in all-optical rings, (Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30 - April 3, 2003 (2003), IEEE), 1355-1361
[36] Caragiannis, I., Wavelength management in WDM rings to maximize the number of connections, SIAM J. Discrete Math., 23, 2, 959-978 (2009) · Zbl 1210.68073
[37] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039
[38] Itai, A.; Rodeh, M.; Tanimoto, S. L., Some Matching Problems for Bipartite Graphs, J. ACM, 25, 4, 517-525 (1978) · Zbl 0388.68059
[39] Rusu, I., Maximum weight edge-constrained matchings, Discrete Appl. Math., 156, 5, 662-672 (2008) · Zbl 1135.68026
[40] Zaker, M., Maximum transversal in partial Latin squares and rainbow matchings, Discrete Appl. Math., 155, 4, 558-565 (2007) · Zbl 1161.05017
[41] Woolbright, D. E., An n x n latin square has a transversal with at least n - square root of n distinct symbols, J. Combin. Theory Ser. A, 24, 2, 235-237 (1978) · Zbl 0368.05012
[42] Le, V. B.; Pfender, F., Complexity results for rainbow matchings, Theor. Comput. Sci., 524, 27-33 (2014) · Zbl 1282.68195
[43] Mestre, J., Greedy in approximation algorithms, (Azar, Y.; Erlebach, T., Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings. Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings, Lecture Notes in Computer Science, vol. 4168 (2006), Springer), 528-539 · Zbl 1131.68594
[44] Mastrolilli, M.; Stamoulis, G., Bi-criteria approximation algorithms for restricted matchings, Theoret. Comput. Sci., 540-541, 115-132 (2014) · Zbl 1358.05286
[45] Y.H. Au, L. Tunçel, Complexity analyses of Bienstock-Zuckerberg and Lasserre relaxations on the matching and stable set polytopes, in: Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings, 2011, pp. 14-26.; Y.H. Au, L. Tunçel, Complexity analyses of Bienstock-Zuckerberg and Lasserre relaxations on the matching and stable set polytopes, in: Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings, 2011, pp. 14-26. · Zbl 1298.90054
[46] Stephen, T.; Tunçel, L., On a representation of the matching polytope via semidefinite liftings, Math. Oper. Res., 24, 1, 1-7 (1999) · Zbl 0977.90078
[47] Aguilera, N. E.; Bianchi, S. M.; Nasini, G. L., Lift and project relaxations for the matching and related polytopes, Discrete Appl. Math., 134, 1-3, 193-212 (2004) · Zbl 1032.05106
[48] Vizing, V., On an estimate of the chromatic class of a p-graph, Diskret. Anal., 3, 25-30 (1964), (in Russian)
[49] König, D., Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann., 77, 4, 453-465 (1916), (in German) · JFM 46.0146.03
[50] Wanless, I. M., Transversals in latin squares, Quasigroups Related Syst., 15, 2, 169-190 (2007) · Zbl 1158.05015
[51] Ryser, H. J., Neuere Probleme der Kombinatorik, Vortrage uber Kombinatorik Ober-Wolfach, Mathematisches Forschungsinstitut Oberwolfach, 24-29 (1967), (in German)
[52] Matousek, J.; Nesetril, J., Invitation to Discrete Mathematics (1998), Oxford University Press · Zbl 0901.05001
[53] Schrijver, A., Theory of Linear and Integer Programming (1998), John Wiley & sons · Zbl 0970.90052
[54] Lau, L. C.; Ravi, R.; Singh, M., Iterative Methods in Combinatorial Optimization (2011), Cambridge University Press · Zbl 1247.90002
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.