{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T02:11:52Z","timestamp":1777342312168,"version":"3.51.4"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,4,20]],"date-time":"2011-04-20T00:00:00Z","timestamp":1303257600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1007\/s10107-011-0451-5","type":"journal-article","created":{"date-parts":[[2011,4,19]],"date-time":"2011-04-19T03:32:55Z","timestamp":1303183975000},"page":"123-148","source":"Crossref","is-referenced-by-count":52,"title":["On linear and semidefinite programming relaxations for hypergraph matching"],"prefix":"10.1007","volume":"135","author":[{"given":"Yuk Hei","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lap Chi","family":"Lau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,4,20]]},"reference":[{"issue":"1","key":"451_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s004930170001","volume":"21","author":"R. Aharoni","year":"2001","unstructured":"Aharoni R.: Ryser\u2019s conjecture for tripartite 3-graphs. Combinatorica 21(1), 1\u20134 (2001)","journal-title":"Combinatorica"},{"key":"451_CR2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V","volume":"35","author":"R. Aharoni","year":"2000","unstructured":"Aharoni R., Haxell P.: Hall\u2019s theorem for hypergraphs. J. Graph Theory 35, 83\u201388 (2000)","journal-title":"J. Graph Theory"},{"issue":"3","key":"451_CR3","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/BF01581168","volume":"80","author":"N. Alon","year":"1998","unstructured":"Alon N., Kahale N.: Approximating the independence number via the $${\\vartheta}$$ -function. Math. Program. 80(3), 253\u2013264 (1998)","journal-title":"Math. Program."},{"issue":"3","key":"451_CR4","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1287\/moor.23.3.640","volume":"23","author":"E.M. Arkin","year":"1998","unstructured":"Arkin E.M., Hassin R.: On local search for weighted k-Set packing. Math. Oper. Res. 23(3), 640\u2013648 (1998)","journal-title":"Math. Oper. Res."},{"key":"451_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Bollob\u00e1s, B., Lov\u00e1sz, L.: Proving integrality gaps without knowing the linear program. In: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 313\u2013322 (2002)","DOI":"10.1109\/SFCS.2002.1181954"},{"key":"451_CR6","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Feige, U., Saberi, A.: Santa claus meets hypergraph matchings. In: Proceedings of APPROX 2008, pp. 10\u201320 (2008)","DOI":"10.1007\/978-3-540-85363-3_2"},{"issue":"4","key":"451_CR7","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/1041680.1041683","volume":"36","author":"R. Bar-Yehuda","year":"2004","unstructured":"Bar-Yehuda R., Bendel K., Freund A., Rawitz D.: Local ratio: a unified framework for approximation algorithms. In memoriam: Shimon Even 1935\u20132004. ACM Comput. Surv. 36(4), 422\u2013463 (2004)","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"451_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703437843","volume":"36","author":"R. Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda R., Halld\u00f3rsson M.M., Naor J.(S.), Shachnai H., Shapira I.: Scheduling split intervals. SIAM J. Comput. 36(1), 1\u201315 (2006)","journal-title":"SIAM J. Comput."},{"key":"451_CR9","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The santa claus problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 31\u201340 (2006)","DOI":"10.1145\/1132516.1132522"},{"key":"451_CR10","doi-asserted-by":"crossref","unstructured":"Berman, P.: A d\/2 approximation for maximum weight independent set in d-claw free graphs. In: Proceedings of the 7th Scandinavian Workshop on Algorithms Theory (SWAT). Lecture Notes in Computer Science, vol. 1851, pp. 31\u201340, Springer, Berlin (2000)","DOI":"10.1007\/3-540-44985-X_19"},{"key":"451_CR11","unstructured":"Berman, P., F\u00fcrer, M.: Approximating maximum independent set in bounded degree graphs. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 365\u2013371 (1994)"},{"key":"451_CR12","unstructured":"Berman, P., Karpinski, M.: Improved approximation lower bound on small occurrence optimization. Electronic Colloquium on Computational Complexity, Report No. 8 (2003)"},{"key":"451_CR13","unstructured":"Berman, P., Krysta, P.: Optimizing misdirection. In: Proceedings of the 14th Annual Symposium on Discrete Algorithms (SODA), pp. 192\u2013201 (2003)"},{"key":"451_CR14","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.disopt.2004.03.002","volume":"1","author":"D. Bienstock","year":"2004","unstructured":"Bienstock D., Ozbay N.: Tree-width and the Sherali-Adams operator. Discret. Optim. 1, 13\u201321 (2004)","journal-title":"Discret. Optim."},{"key":"451_CR15","first-page":"87","volume":"12","author":"M. Ca\u0142czy\u0144ska-Kar\u0142owicz","year":"1964","unstructured":"Ca\u0142czy\u0144ska-Kar\u0142owicz M.: Theorem on families of finite sets. Bulletin de l\u2019Acad\u00e9mie Polonaise des Sciences. S\u00e9rie des Sciences Math\u00e9matiques, Astronomiques et Physiques 12, 87\u201389 (1964)","journal-title":"Bulletin de l\u2019Acad\u00e9mie Polonaise des Sciences. S\u00e9rie des Sciences Math\u00e9matiques, Astronomiques et Physiques"},{"key":"451_CR16","unstructured":"Chandra, B., Halld\u00f3rsson, M.M.: Greedy local improvement and weighted set packing approximation. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 169\u2013176 (1999)"},{"key":"451_CR17","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Local global tradeoffs in metric embeddings. In: Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS), pp. 713\u2013723 (2007)","DOI":"10.1109\/FOCS.2007.64"},{"key":"451_CR18","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 283\u2013292 (2009)","DOI":"10.1145\/1536414.1536455"},{"issue":"7","key":"451_CR19","doi-asserted-by":"crossref","first-page":"1396","DOI":"10.1016\/j.dam.2008.10.017","volume":"157","author":"F. Chataigner","year":"2008","unstructured":"Chataigner F., Manic G., Wakabayashi Y., Yuster R.: Approximation algorithms and hardness results for the clique packing problem. Discret. Appl. Math. 157(7), 1396\u20131406 (2008)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"451_CR20","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1017\/S0963548305006826","volume":"14","author":"A. Coja-Oghlan","year":"2005","unstructured":"Coja-Oghlan A.: The Lov\u00e1sz number of random graphs. Comb. Probab. Comput. 14(4), 439\u2013465 (2005)","journal-title":"Comb. Probab. Comput."},{"key":"451_CR21","unstructured":"Erd\u00f6s, P., Lov\u00e1sz, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In: Hajnal, A., Rado, R, S\u00f3s, V.T. (eds.) Proceedings of Colloquia Mathematica Societatis J\u00e1nos Bolyai, Infinite and Finite Sets. vol. 10, pp. 609\u2013627. Keszthely, Hungary (1973)"},{"key":"451_CR22","doi-asserted-by":"crossref","unstructured":"Feige, U.: Randomized graph products, chromatic numbers, and the Lov\u00e1sz $${\\vartheta}$$ -function. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pp. 635\u2013640 (1995)","DOI":"10.1145\/225058.225281"},{"issue":"2","key":"451_CR23","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/S009753970240118X","volume":"32","author":"U. Feige","year":"2003","unstructured":"Feige U., Krauthgamer R.: The probable value of the Lov\u00e1sz\u2013Schrijver relaxations for maximum independent set. SIAM J. Comput. 32(2), 345\u2013370 (2003)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"451_CR24","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02579271","volume":"1","author":"Z. F\u00fcredi","year":"1981","unstructured":"F\u00fcredi Z.: Maximum degree and fractional matchings in uniform hypergraphs. Combinatorica 1(2), 155\u2013162 (1981)","journal-title":"Combinatorica"},{"issue":"2","key":"451_CR25","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF01303202","volume":"13","author":"Z. F\u00fcredi","year":"1993","unstructured":"F\u00fcredi Z., Kahn J., Seymour P.: On the fractional matching polytope of a hypergraph. Combinatorica 13(2), 167\u2013180 (1993)","journal-title":"Combinatorica"},{"key":"451_CR26","unstructured":"Gomes, C.P., Regis, R.G., Shmoys, D.B.: An improved approximation algorithm for the partial latin square problem. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 832\u2013833 (2003)"},{"key":"451_CR27","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel M., Lov\u00e1sz L., Schrijver A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorics 1, 169\u2013197 (1981)","journal-title":"Combinatorics"},{"key":"451_CR28","first-page":"325","volume":"21","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel M., Lov\u00e1sz L., Schrijver A.: Polynomial algorithms for perfect graphs. Ann. Discret. Math. 21, 325\u2013356 (1984)","journal-title":"Ann. Discret. Math."},{"key":"451_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel M., Lov\u00e1sz L., Schrijver A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988)"},{"key":"451_CR30","unstructured":"Halld\u00f3rsson, M.H.: Approximating discrete collections via local improvments. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 160\u2013169 (1995)"},{"issue":"1","key":"451_CR31","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02523693","volume":"18","author":"M.M. Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson M.M., Radhakrishnan J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18(1), 145\u2013163 (1997)","journal-title":"Algorithmica"},{"key":"451_CR32","doi-asserted-by":"crossref","unstructured":"Hajirasouliha, I., Jowhari, H., Kumar, R., Sundaram, R.: On completing latin squares. In: Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 4393, pp. 524\u2013535. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-70918-3_45"},{"issue":"6","key":"451_CR33","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1016\/j.dam.2005.11.003","volume":"154","author":"R. Hassin","year":"2006","unstructured":"Hassin R., Rubinstein S.: An approximation algorithm for maximum triangle packing. Discret. Appl. Math. 154(6), 971\u2013979 (2006)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"451_CR34","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad J.: Clique is hard to approximate within $${n^{1-\\epsilon}}$$ . Acta Math 182(1), 105\u2013142 (1999)","journal-title":"Acta Math"},{"key":"451_CR35","unstructured":"Hazan, E., Safra, M., Schwartz, O.: On the complexity of approximating k-dimensional matching. In: Proceedings of APPROX 2003, Lecture Notes in Computer Science, vol. 2764, pp. 59\u201370. Springer, Berlin (2003)"},{"issue":"1","key":"451_CR36","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E. Hazan","year":"2006","unstructured":"Hazan E., Safra M., Schwartz O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20\u201339 (2006)","journal-title":"Comput. Complex."},{"key":"451_CR37","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"Hurkens C.A.J., Schrijver A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discret. Math. 2, 68\u201372 (1989)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"451_CR38","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K. Jain","year":"2001","unstructured":"Jain K.: A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica 21(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"issue":"1","key":"451_CR39","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"Kann V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett. 37(1), 27\u201335 (1991)","journal-title":"Inf. Process. Lett."},{"key":"451_CR40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/1193","volume":"1","author":"D.E. Knuth","year":"1994","unstructured":"Knuth D.E.: The sandwich theorem. Electron. J. Comb. 1, 1\u201349 (1994)","journal-title":"Electron. J. Comb."},{"issue":"3","key":"451_CR41","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M. Laurent","year":"2003","unstructured":"Laurent M.: A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28(3), 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"451_CR42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"451_CR43","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz L., Schrijver A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"451_CR44","doi-asserted-by":"crossref","unstructured":"Magen, A., Moharrami, M.: Robust algorithms for maximum independent set on minor-free graphs based on the Sherali-Adams hierarchy. In: Proceedings of APPROX 2009, pp. 258\u2013271 (2009)","DOI":"10.1007\/978-3-642-03685-9_20"},{"key":"451_CR45","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Sinclair, A.: Sherali-Adams relaxations of the matching polytope. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 293\u2013302 (2009)","DOI":"10.1145\/1536414.1536456"},{"key":"451_CR46","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198570431.001.0001","volume-title":"An Invitation to Discrete Mathematics","author":"J. Matou\u0161ek","year":"2008","unstructured":"Matou\u0161ek J., Ne\u0161e\u0159ril J.: An Invitation to Discrete Mathematics. Clarendon Press, Oxford (2008)"},{"issue":"1","key":"451_CR47","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"M.W. Padberg","year":"1973","unstructured":"Padberg M.W.: On the facial structure of set packing polyhedra. Math. Program. 5(1), 199\u2013215 (1973)","journal-title":"Math. Program."},{"key":"451_CR48","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level lasserre lower bounds for certain k-CSPs. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 593\u2013602 (2008)","DOI":"10.1109\/FOCS.2008.74"},{"key":"451_CR49","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 453\u2013461 (2001)","DOI":"10.1145\/380752.380839"},{"key":"451_CR50","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: CSP gaps and reductions in the lasserre hierarchy. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 303\u2013312 (2009)","DOI":"10.1145\/1536414.1536457"},{"key":"451_CR51","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/0095-8956(85)90043-7","volume":"39","author":"Zs. Tuza","year":"1985","unstructured":"Tuza Zs.: Critical hypergraphs and intersecting set-pair systems. J. Comb. Theory (B) 39, 134\u2013145 (1985)","journal-title":"J. Comb. Theory (B)"},{"key":"451_CR52","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0166-218X(87)90074-6","volume":"16","author":"Zs. Tuza","year":"1987","unstructured":"Tuza Zs.: On two intersecting set systems and k-continuous boolean functions. Discret. Appl. Math. 16, 183\u2013185 (1987)","journal-title":"Discret. Appl. Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-011-0451-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-011-0451-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-011-0451-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T04:16:13Z","timestamp":1741148173000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-011-0451-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,20]]},"references-count":52,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["451"],"URL":"https:\/\/doi.org\/10.1007\/s10107-011-0451-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,20]]}}}