{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:33:31Z","timestamp":1750307611558,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,3,1]],"date-time":"2009-03-01T00:00:00Z","timestamp":1235865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["NSF\/DBI-0354771NSF\/ITR-IIS-0407204"],"award-info":[{"award-number":["NSF\/DBI-0354771NSF\/ITR-IIS-0407204"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["6.07E+23"],"award-info":[{"award-number":["6.07E+23"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000153","name":"Division of Biological Infrastructure","doi-asserted-by":"publisher","award":["NSF\/DBI-0354771NSF\/ITR-IIS-0407204"],"award-info":[{"award-number":["NSF\/DBI-0354771NSF\/ITR-IIS-0407204"]}],"id":[{"id":"10.13039\/100000153","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["N_CityU 102\/01"],"award-info":[{"award-number":["N_CityU 102\/01"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p>We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion, namely the maximum number of paths that use any single edge in a cycle, is minimized.<\/jats:p>\n          <jats:p>\n            The\n            <jats:italic>minimum congestion hypergraph embedding in a cycle<\/jats:italic>\n            problem is known to be NP-hard and its graph version, the\n            <jats:italic>minimum congestion graph embedding in a cycle<\/jats:italic>\n            , is solvable in polynomial-time. Furthermore, for the graph problem, a polynomial-time approximation scheme for the weighted version is known. For the hypergraph model, several approximation algorithms with a ratio of two have been previously published. A recent paper reduced the approximation ratio to 1.5. We present a polynomial-time approximation scheme in this article, settling the debate regarding whether the problem is polynomial-time approximable.\n          <\/jats:p>","DOI":"10.1145\/1497290.1497296","type":"journal-article","created":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T16:34:22Z","timestamp":1239035662000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A polynomial-time approximation scheme for embedding hypergraph in a cycle"],"prefix":"10.1145","volume":"5","author":[{"given":"Guojun","family":"Li","sequence":"first","affiliation":[{"name":"Shandong University, Jinan, China; University of Georgia, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaotie","family":"Deng","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Georgia, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,3,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90046-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.589233"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00117-3"},{"volume-title":"Proceedings of the 10th International Conference on High Performance Computing, 85--94","author":"Gu Q. P.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/bltj.2047"},{"volume-title":"Proceedings of the 1st International Symposium on Cyber World (CW'02)","author":"Lee S. L.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2005.62"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506150"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90007-W"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80012-3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199601)8:1%3C27::AID-RSA2%3E3.0.CO;2-T"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497290.1497296","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1497290.1497296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:40Z","timestamp":1750250740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497290.1497296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1145\/1497290.1497296"],"URL":"https:\/\/doi.org\/10.1145\/1497290.1497296","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2009,3]]},"assertion":[{"value":"2005-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}