{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:12:41Z","timestamp":1787508761969,"version":"build-2736575974"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2013,9,12]],"date-time":"2013-09-12T00:00:00Z","timestamp":1378944000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,11]]},"abstract":"\n For\n k<\/jats:italic>\n -graphs\n F<\/jats:italic>\n 0<\/jats:sub>\n and\n H<\/jats:italic>\n , an\n F<\/jats:italic>\n 0<\/jats:sub>\n -packing of\n H<\/jats:italic>\n is a family\n \n \n \n $\\mathscr{F}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of pairwise edge-disjoint copies of\n F<\/jats:italic>\n 0<\/jats:sub>\n in\n H<\/jats:italic>\n . Let \u03bd\n \n F<\/jats:italic>\n 0<\/jats:sub>\n <\/jats:sub>\n (\n H<\/jats:italic>\n ) denote the maximum size |\n \n \n \n $\\mathscr{F}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n | of an\n F<\/jats:italic>\n 0<\/jats:sub>\n -packing of\n H<\/jats:italic>\n . Already in the case of graphs, computing \u03bd\n \n F<\/jats:italic>\n 0<\/jats:sub>\n <\/jats:sub>\n (\n H<\/jats:italic>\n ) is NP-hard for most fixed\n F<\/jats:italic>\n 0<\/jats:sub>\n (Dor and Tarsi [6]).\n <\/jats:p>\n \n In this paper, we consider the case when\n F<\/jats:italic>\n 0<\/jats:sub>\n is a fixed linear\n k<\/jats:italic>\n -graph. We establish an algorithm which, for \u03b6 > 0 and a given\n k<\/jats:italic>\n -graph\n H<\/jats:italic>\n , constructs in time polynomial in |\n V(H)<\/jats:italic>\n | an\n F<\/jats:italic>\n 0<\/jats:sub>\n -packing of\n H<\/jats:italic>\n of size at least \u03bd\n \n F<\/jats:italic>\n 0<\/jats:sub>\n <\/jats:sub>\n (\n H<\/jats:italic>\n ) \u2212 \u03b6 |\n V(H)<\/jats:italic>\n |\n \n k<\/jats:sup>\n <\/jats:italic>\n . Our result extends one of Haxell and R\u00f6dl, who established the analogous algorithm for graphs.\n <\/jats:p>","DOI":"10.1017\/s0963548313000291","type":"journal-article","created":{"date-parts":[[2013,9,12]],"date-time":"2013-09-12T05:12:47Z","timestamp":1378962767000},"page":"829-858","source":"Crossref","is-referenced-by-count":1,"title":["Constructive Packings by Linear Hypergraphs"],"prefix":"10.1017","volume":"22","author":[{"given":"JILL","family":"DIZONA","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"BRENDAN","family":"NAGLE","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2013,9,12]]},"reference":[{"key":"S0963548313000291_ref4","unstructured":"Czygrinow A. Personal communication."},{"key":"S0963548313000291_ref14","doi-asserted-by":"crossref","unstructured":"Haxell P. E. , Nagle B. and R\u00f6dl V. (2005) An algorithmic version of the hypergraph regularity method [extended abstract]. In Proc. 46th Annual IEEE Symposium on Foundations of Computer Science: FOCS '05, pp. 439\u2013448.","DOI":"10.1109\/SFCS.2005.17"},{"key":"S0963548313000291_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799351729"},{"key":"S0963548313000291_ref15","doi-asserted-by":"publisher","DOI":"10.1137\/060652385"},{"key":"S0963548313000291_ref23","doi-asserted-by":"crossref","first-page":"199","DOI":"10.4064\/aa-27-1-199-245","article-title":"On sets of integers containing no k elements in arithmetic progression.","volume":"27","author":"Szemer\u00e9di","year":"1975","journal-title":"Acta Arithmetica"},{"key":"S0963548313000291_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00181-0"},{"key":"S0963548313000291_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20389"},{"key":"S0963548313000291_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408223"},{"key":"S0963548313000291_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.05.005"},{"key":"S0963548313000291_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.006"},{"key":"S0963548313000291_ref24","first-page":"399","volume-title":"Probl\u00e8mes en Combinatoires et Th\u00e9orie des Graphes: Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976","author":"Szemer\u00e9di","year":"1978"},{"key":"S0963548313000291_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007236"},{"key":"S0963548313000291_ref26","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20048"},{"key":"S0963548313000291_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"S0963548313000291_ref19","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.26"},{"key":"S0963548313000291_ref6","first-page":"252","volume-title":"Proc. 20th ACM STOC","author":"Dor","year":"1992"},{"key":"S0963548313000291_ref10","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2007.166.897"},{"key":"S0963548313000291_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10017"},{"key":"S0963548313000291_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20017"},{"key":"S0963548313000291_ref2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"S0963548313000291_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02351586"},{"key":"S0963548313000291_ref1","volume-title":"The Probabilistic Method","author":"Alon","year":"1992"},{"key":"S0963548313000291_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548313000291_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-004-0556-1"},{"key":"S0963548313000291_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170003"},{"key":"S0963548313000291_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10075"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000291","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T15:19:46Z","timestamp":1556032786000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000291\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,12]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["S0963548313000291"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000291","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,12]]}}}