{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T09:06:11Z","timestamp":1762938371389,"version":"3.45.0"},"reference-count":19,"publisher":"Wiley","issue":"25-26","license":[{"start":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:00:00Z","timestamp":1760400000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2025,11,30]]},"abstract":"<jats:title>ABSTRACT<\/jats:title>\n                  <jats:p>\n                    Given two distinct sets of items and a set of agents, each with combined preferences for selecting one item from each set, the question arises: How can we optimally assign pairs of items to agents? To address this, we investigate the popular matching problem in a 3\u2010uniform 3\u2010partite hypergraph. In this setting, the first partition represents agents, while the second and third partitions represent two different types of items. Agents express preferences over the hyperedges incident to them, whereas the items have no preferences. A matching  is called\n                    <jats:italic>popular<\/jats:italic>\n                    if there exists no matching  that a majority of agents prefer over . Since determining the existence of a popular matching is NP\u2010hard in a 3\u2010uniform 3\u2010partite hypergraph, we focus on approximating such matchings using the concept of\n                    <jats:italic>unpopularity factor<\/jats:italic>\n                    . The unpopularity factor is defined as the maximum ratio  over all other matchings , where  and  are the sets of agents preferring the matching  and , respectively. We first present an exact algorithm that computes a popular matching in exponential time if it exists, or it notifies the nonexistence of such a matching. To address efficiency, we design an approximation algorithm that constructs a matching  in a 3\u2010uniform 3\u2010partite hypergraph with unpopularity factor , where  is the maximum degree of any agent. Additionally, we show that , where  is the number of agents, implying . The approximation algorithm runs in  time, where  is the number of hyperedges.\n                  <\/jats:p>","DOI":"10.1002\/cpe.70331","type":"journal-article","created":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T06:44:42Z","timestamp":1760510682000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Algorithm for Matching in a (3,3)\u2010Hypergraph With One\u2010Sided Preferences Having Quadratic Unpopularity Factor"],"prefix":"10.1002","volume":"37","author":[{"given":"Yashdeep","family":"Singh","sequence":"first","affiliation":[{"name":"Department of Computer Science &amp; Engineering Indian Institute of Technology Guwahati  Guwahati India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sushanta","family":"Karmakar","sequence":"additional","affiliation":[{"name":"Department of Computer Science &amp; Engineering Indian Institute of Technology Guwahati  Guwahati India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2025,10,14]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CANDARW64572.2024.00040"},{"key":"e_1_2_8_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.03.028"},{"key":"e_1_2_8_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CANDARW60564.2023.00028"},{"key":"e_1_2_8_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9434-9"},{"key":"e_1_2_8_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/bs.3830200304"},{"key":"e_1_2_8_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1076162"},{"key":"e_1_2_8_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/06067328X"},{"key":"e_1_2_8_9_1","first-page":"593","volume-title":"Proceedings of the 8th Latin American Conference on Theoretical Informatics","author":"McCutchen R. M.","year":"2008"},{"key":"e_1_2_8_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.012"},{"key":"e_1_2_8_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00256-5_25"},{"key":"e_1_2_8_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-024-01215-6"},{"key":"e_1_2_8_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.174"},{"key":"e_1_2_8_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/110852838"},{"key":"e_1_2_8_15_1","unstructured":"\u00c1.CsehandJ.Peters \u201cThree\u2010Dimensional Popular Matching With Cyclic Preferences \u201darXiv Preprint arXiv:2105.09115 (2021)."},{"key":"e_1_2_8_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3491003.3491305"},{"key":"e_1_2_8_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9287-9"},{"key":"e_1_2_8_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"e_1_2_8_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_8_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.70331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T09:03:13Z","timestamp":1762938193000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.70331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,14]]},"references-count":19,"journal-issue":{"issue":"25-26","published-print":{"date-parts":[[2025,11,30]]}},"alternative-id":["10.1002\/cpe.70331"],"URL":"https:\/\/doi.org\/10.1002\/cpe.70331","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"type":"print","value":"1532-0626"},{"type":"electronic","value":"1532-0634"}],"subject":[],"published":{"date-parts":[[2025,10,14]]},"assertion":[{"value":"2025-05-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-27","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e70331"}}