{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:24:02Z","timestamp":1767140642339,"version":"build-2238731810"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T00:00:00Z","timestamp":1575244800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T00:00:00Z","timestamp":1575244800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"GRAMM","award":["TIN2017-86727-C2-1-R"],"award-info":[{"award-number":["TIN2017-86727-C2-1-R"]}]},{"DOI":"10.13039\/501100005302","name":"Alexander S. Onassis Public Benefit Foundation","doi-asserted-by":"publisher","award":["NA"],"award-info":[{"award-number":["NA"]}],"id":[{"id":"10.13039\/501100005302","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s10472-019-09671-5","type":"journal-article","created":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T11:30:12Z","timestamp":1575286212000},"page":"133-155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Directed Lov\u00e1sz local lemma and Shearer\u2019s lemma"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4912-8959","authenticated-orcid":false,"given":"Lefteris","family":"Kirousis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Livieratos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kostas I.","family":"Psaromiligkos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,2]]},"reference":[{"key":"9671_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Iliopoulos, F.: Random walks that find perfect objects and the Lov\u00e1sz local lemma. In: Proceedings 55th Annual Symposium on Foundations of Computer Science (FOCS), pp 494\u2013503. IEEE (2014)","DOI":"10.1109\/FOCS.2014.59"},{"issue":"3","key":"9671_CR2","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/2818352","volume":"63","author":"D Achlioptas","year":"2016","unstructured":"Achlioptas, D., Iliopoulos, F.: Random walks that find perfect objects and the Lov\u00e1sz local lemma. J. ACM (JACM) 63(3), 22 (2016)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"9671_CR3","doi-asserted-by":"publisher","first-page":"33","DOI":"10.37236\/1371","volume":"5","author":"EA Bender","year":"1998","unstructured":"Bender, E.A., Bruce Richmond, L: A multivariate Lagrange inversion formula for asymptotic calculations. Electron. J. Comb. 5(1), 33 (1998)","journal-title":"Electron. J. Comb."},{"key":"9671_CR4","first-page":"609","volume":"10","author":"P Erdo\u030bs","year":"1975","unstructured":"Erdo\u030bs, P., Lov\u00e1sz, L.: Problems and results on 3-chromatic hypergraphs and some related questions. Infinite Finite Sets 10, 609\u2013627 (1975)","journal-title":"Infinite Finite Sets"},{"issue":"2\u20133","key":"9671_CR5","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0166-218X(91)90040-4","volume":"30","author":"P Erdo\u030bs","year":"1991","unstructured":"Erdo\u030bs, P., Spencer, J.: Lopsided Lov\u00e1sz local lemma and Latin transversals. Discret. Appl. Math. 30(2\u20133), 151\u2013154 (1991)","journal-title":"Discret. Appl. Math."},{"key":"9671_CR6","unstructured":"Giotis, I., Kirousis, L., Psaromiligkos, K.I., Thilikos, D.M.: On the algorithmic Lov\u00e1sz local lemma and acyclic edge coloring. In: Proceedings of the twelfth workshop on analytic algorithmics and combinatorics. Society for Industrial and Applied Mathematics (2015) Available: http:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611973761.2"},{"key":"9671_CR7","unstructured":"Giotis, I., Kirousis, L.M., Livieratos, J., Psaromiligkos, K.I., Thilikos, D.M.: Alternative proofs of the asymmetric Lov\u00e1sz local lemma and Shearer\u2019s lemma. In: Proceedings of the 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures, GASCom (2018) Available: http:\/\/ceur-ws.org\/Vol-2113\/paper15.pdf"},{"key":"9671_CR8","unstructured":"Giotis, I., Kirousis, L.M., Psaromiligkos, K.I., Thilikos, D.: An alternative proof for the constructive asymmetric Lov\u00e1sz local lemma. In: 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization (2015)"},{"key":"9671_CR9","doi-asserted-by":"crossref","unstructured":"Harris, D.G.: Lopsidependency in the Moser-Tardos framework: Beyond the lopsided Lov\u00e1sz local lemma. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1792\u20131808. SIAM (2015)","DOI":"10.1137\/1.9781611973730.120"},{"key":"9671_CR10","doi-asserted-by":"crossref","unstructured":"Harris, D.G, Srinivasan, A.: A constructive algorithm for the Lov\u00e1sz local lemma on permutations. In: Proceedings 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 907\u2013925. SIAM (2014)","DOI":"10.1137\/1.9781611973402.68"},{"key":"9671_CR11","doi-asserted-by":"crossref","unstructured":"Harvey, N.J.A., Vondr\u00e1k, J.: An algorithmic proof of the Lov\u00e1sz local lemma via resampling oracles. In: Proceedings 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1327\u20131346. IEEE (2015)","DOI":"10.1109\/FOCS.2015.85"},{"key":"9671_CR12","doi-asserted-by":"crossref","unstructured":"He, K., Li, L., Liu, X., Wang, Y., Xia, M.: Variable-version Lov\u00e1sz local: Beyond shearer\u2019s bound. In: 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 451\u2013462. IEEE (2017)","DOI":"10.1109\/FOCS.2017.48"},{"key":"9671_CR13","unstructured":"Horn, R.A, Johnson, C.R: Matrix Analysis. Cambridge University Press (1990)"},{"key":"9671_CR14","doi-asserted-by":"crossref","unstructured":"Kolipaka, K., Rao, B., Szegedy, M.: Moser and Tardos meet Lov\u00e1sz. In: Proceedings 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 235\u2013244. ACM (2011)","DOI":"10.1145\/1993636.1993669"},{"key":"9671_CR15","doi-asserted-by":"crossref","unstructured":"Moser, R.A.: A constructive proof of the Lov\u00e1sz local lemma. In: Proceedings 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 343\u2013350. ACM (2009)","DOI":"10.1145\/1536414.1536462"},{"issue":"2","key":"9671_CR16","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1667053.1667060","volume":"57","author":"RA Moser","year":"2010","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general Lov\u00e1sz local lemma. J. ACM (JACM) 57(2), 11 (2010)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"9671_CR17","doi-asserted-by":"publisher","first-page":"1277","DOI":"10.1137\/16M1067767","volume":"31","author":"K Sarkar","year":"2017","unstructured":"Sarkar, K., Colbourn, C.J: Upper bounds on the size of covering arrays. SIAM J. Discret. Math. 31(2), 1277\u20131293 (2017)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"9671_CR18","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02579368","volume":"5","author":"JB Shearer","year":"1985","unstructured":"Shearer, J.B.: On a problem of Spencer. Combinatorica 5(3), 241\u2013245 (1985)","journal-title":"Combinatorica"},{"key":"9671_CR19","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: The Lov\u00e1sz local lemma\u2013a survey. In: International Computer Science Symposium in Russia, pp. 1\u201311. Springer (2013)","DOI":"10.1007\/978-3-642-38536-0_1"},{"key":"9671_CR20","unstructured":"Tao, T.: Moser\u2019s entropy compression argument (2009) Available: https:\/\/terrytao.wordpress.com\/2009\/08\/05\/mosers-entropy-compression-argument\/"}],"updated-by":[{"DOI":"10.1007\/s10472-020-09715-1","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T00:00:00Z","timestamp":1604880000000}}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-019-09671-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-019-09671-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-019-09671-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T10:56:40Z","timestamp":1613041000000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-019-09671-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,2]]},"references-count":20,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["9671"],"URL":"https:\/\/doi.org\/10.1007\/s10472-019-09671-5","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,2]]},"assertion":[{"value":"2 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2020","order":2,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":4,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10472-020-09715-1","URL":"https:\/\/doi.org\/10.1007\/s10472-020-09715-1","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}