{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:54Z","timestamp":1750219854764,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            In this article, we study the classic\n            <jats:sc>\n              Weighted 3-Set\n              <jats:italic>k<\/jats:italic>\n              -Packing\n            <\/jats:sc>\n            problem: given a universe\n            <jats:italic>U<\/jats:italic>\n            , a family\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( {\\mathcal {S}}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            of subsets of size 3 of\n            <jats:italic>U<\/jats:italic>\n            , a weight function\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(w : {\\mathcal {S}} \\rightarrow \\mathbb {R}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            ,\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(W \\in \\mathbb {R}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , and a parameter\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k \\in \\mathbb {N}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , the objective is to decide if there is a subfamily\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( {\\mathcal {S}}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            <jats:sup>\u2032<\/jats:sup>\n            \u2286\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( {\\mathcal {S}}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            of\n            <jats:italic>k<\/jats:italic>\n            disjoint sets and total weight at least\n            <jats:italic>W<\/jats:italic>\n            . We present a deterministic parameterized algorithm for this problem that runs in time\n            <jats:italic>O<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            (8.097\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ), where\n            <jats:italic>O<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            hides factors polynomial in the input size. This substantially improves upon the previously best deterministic algorithm for\n            <jats:sc>\n              Weighted 3-Set\n              <jats:italic>k<\/jats:italic>\n              -Packing\n            <\/jats:sc>\n            , which runs in time\n            <jats:italic>O<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            (12.155\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) SIDMA [\n            <jats:xref ref-type=\"bibr\">18<\/jats:xref>\n            ], and was also the best deterministic algorithm for the unweighted version of this problem. Our algorithm is based on a novel application of the method of representative sets that might be of independent interest.\n          <\/jats:p>","DOI":"10.1145\/3599722","type":"journal-article","created":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T12:15:03Z","timestamp":1692188103000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Forgetfulness Can Make You Faster: An\n            <b>\n              <i>O<\/i>\n              <sup>*<\/sup>\n              (8.097\n              <sup>\n                <i>k<\/i>\n              <\/sup>\n              )\n            <\/b>\n            -time Algorithm\u00a0for Weighted 3-set\n            <b>\n              <i>k<\/i>\n            <\/b>\n            -packing"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3636-5322","authenticated-orcid":false,"given":"Meirav","family":"Zehavi","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negeb, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.04.020"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.03.003"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01904851"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.042"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1096-z"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/080716475"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_9_2","first-page":"68","volume-title":"SODA","author":"Dell H.","year":"2012","unstructured":"H. Dell and D. Marx. 2012. Kernelization of packing problems. In SODA. 68\u201381."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"2","key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s00453-007-9146-y","article-title":"Faster fixed-parameter tractable algorithms for matching and packing problems.","volume":"52","author":"Fellows M.","year":"2008","unstructured":"M. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, D. Thilikos, and S. Whitesides. 2008. Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica 52, 2 (2008), 167\u2013176.","journal-title":"Algorithmica"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.12.011"},{"key":"e_1_3_2_14_2","article-title":"Randomized parameterized algorithms for  \\(P_2\\) -packing and co-path packing problems","author":"Feng Q.","year":"2013","unstructured":"Q. Feng, J. Wang, S. Li, and J. Chen. 2013. Randomized parameterized algorithms for \\(P_2\\) -packing and co-path packing problems. J. Comb. Optim. 29 (2013), 125\u2013140.","journal-title":"J. Comb. Optim."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9230-0"},{"issue":"1","key":"e_1_3_2_16_2","doi-asserted-by":"crossref","DOI":"10.1145\/3293466","article-title":"Subquadratic kernels for implicit 3-hitting set and 3-set packing problems","volume":"15","author":"Fomin F. V.","year":"2019","unstructured":"F. V. Fomin, T. N. Le, D. Lokshtanov, S. Saurabh, S. Thomass\u00e9, and M. Zehavi. 2019. Subquadratic kernels for implicit 3-hitting set and 3-set packing problems. ACM Trans. Algorithms 15, 1 (2019), 13:1\u201313:44.","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","DOI":"10.1145\/2886094","article-title":"Efficient computation of representative families with applications in parameterized and exact algorithms","volume":"63","author":"Fomin F. V.","year":"2016","unstructured":"F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh. 2016. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63, 4 (2016), 29:1\u201329:60.","journal-title":"J. ACM"},{"key":"e_1_3_2_18_2","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"Fomin F. V.","year":"2019","unstructured":"F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi. 2019. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/140981290"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.12.005"},{"key":"e_1_3_2_21_2","first-page":"575","volume-title":"ICALP","author":"Koutis I.","year":"2008","unstructured":"I. Koutis. 2008. Faster algebraic algorithms for path and packing problems. In ICALP. 575\u2013586."},{"key":"e_1_3_2_22_2","first-page":"575","volume-title":"TAMC","author":"Liu Y.","year":"2007","unstructured":"Y. Liu, J. Chen, and J. Wang. 2007. On efficient \\(\\mathrm{FPT}\\) algorithms for weighted matching and packing problems. In TAMC. 575\u2013586."},{"key":"e_1_3_2_23_2","first-page":"84","volume-title":"IWPEC","author":"Liu Y.","year":"2006","unstructured":"Y. Liu, S. Lu, J. Chen, and S. H. Sze. 2006. Greedy localization and color-coding: Improved matching and packing algorithms. In IWPEC. 84\u201395."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.008"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.027"},{"key":"e_1_3_2_26_2","first-page":"239","article-title":"How to find long paths efficiently","volume":"25","author":"Monien B.","year":"1985","unstructured":"B. Monien. 1985. How to find long paths efficiently. Ann. Disc. Math. 25 (1985), 239\u2013254.","journal-title":"Ann. Disc. Math."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.009"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.11.008"},{"key":"e_1_3_2_29_2","first-page":"130","volume-title":"COCOON","author":"Wang J.","year":"2008","unstructured":"J. Wang and Q. Feng. 2008. Improved parameterized algorithms for weighted 3-set packing. In COCOON. 130\u2013139."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.12.048"},{"key":"e_1_3_2_31_2","first-page":"1037","volume-title":"ESA","author":"Zehavi M.","year":"2015","unstructured":"M. Zehavi. 2015. Mixing color coding-related techniques. In ESA. 1037\u20131049."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3599722","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3599722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:11Z","timestamp":1750178831000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3599722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,12]]},"references-count":30,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3599722"],"URL":"https:\/\/doi.org\/10.1145\/3599722","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2023,12,12]]},"assertion":[{"value":"2019-12-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}