{"id":17083,"date":"2026-09-24T13:31:25","date_gmt":"2026-09-24T18:31:25","guid":{"rendered":"https:\/\/uwm.edu\/math\/?post_type=tribe_events&#038;p=17083"},"modified":"2026-09-24T14:21:13","modified_gmt":"2026-09-24T19:21:13","slug":"colloquium-dr-christine-cheng","status":"publish","type":"tribe_events","link":"https:\/\/uwm.edu\/math\/event\/colloquium-dr-christine-cheng\/","title":{"rendered":"Colloquium: Dr. Christine Cheng"},"content":{"rendered":"<h2><span data-olk-copy-source=\"MessageBody\">Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings<\/span><\/h2>\n<div data-olk-copy-source=\"MailCompose\">An instance of the Stable Roommates (SR) problem consists of 2n agents, each with a preference<br \/>\nlist that linearly orders the other agents. The goal is to find a perfect matching that is stable \u2013 one<br \/>\nwith no pair of agents who mutually prefer each other to their assigned partners. In this talk, I<br \/>\nconsider the problem of finding an optimal stable matching. An efficient algorithm exists for Stable Marriage (SM) instances, the bipartite version, but the problem is NP-hard for SR instances. I will sketch a solution showing how an optimal stable matching for an SR instance can be obtained by \u201ccovering\u201d it with SM instances.<br \/>\nIn particular, the closer the SR instance is to an SM instance, the more efficient is the solution.<\/div>\n<div><\/div>\n<div>Check <a href=\"https:\/\/sites.uwm.edu\/ccheng\/\">here<\/a> for more information!<\/div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings An instance of the Stable Roommates (SR) problem consists of 2n agents, each with a preference list that linearly orders the other agents. The &hellip;<\/p>\n","protected":false},"author":30596,"featured_media":0,"template":"","meta":{"_acf_changed":false,"_tribe_events_status":"","_tribe_events_status_reason":"","_tribe_events_is_hybrid":"","_tribe_events_is_virtual":"","_tribe_events_virtual_video_source":"","_tribe_events_virtual_embed_video":"","_tribe_events_virtual_linked_button_text":"","_tribe_events_virtual_linked_button":"","_tribe_events_virtual_show_embed_at":"","_tribe_events_virtual_show_embed_to":[],"_tribe_events_virtual_show_on_event":"","_tribe_events_virtual_show_on_views":"","_tribe_events_virtual_url":"","footnotes":"","uwm_wg_additional_authors":[]},"tags":[],"tribe_events_cat":[41],"class_list":["post-17083","tribe_events","type-tribe_events","status-publish","hentry","tribe_events_cat-colloquia","cat_colloquia"],"uwm_unpublish_requested":false,"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v28.5 (Yoast SEO v28.5) - https:\/\/yoast.com\/product\/yoast-seo-premium-wordpress\/ -->\n<title>Mathematical Sciences<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/uwm.edu\/math\/event\/colloquium-dr-christine-cheng\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Colloquium: Dr. Christine Cheng\" \/>\n<meta property=\"og:description\" content=\"Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings An instance of the Stable Roommates (SR) problem consists of 2n agents, each with a preference list that linearly orders the other agents. The &hellip;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/uwm.edu\/math\/event\/colloquium-dr-christine-cheng\/\" \/>\n<meta property=\"og:site_name\" content=\"Mathematical Sciences\" \/>\n<meta property=\"article:modified_time\" content=\"2026-09-24T19:21:13+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/uwm.edu\\\/math\\\/event\\\/colloquium-dr-christine-cheng\\\/\",\"url\":\"https:\\\/\\\/uwm.edu\\\/math\\\/event\\\/colloquium-dr-christine-cheng\\\/\",\"name\":\"Colloquium: Dr. Christine Cheng - Mathematical Sciences\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/uwm.edu\\\/math\\\/#website\"},\"datePublished\":\"2026-09-24T18:31:25+00:00\",\"dateModified\":\"2026-09-24T19:21:13+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/uwm.edu\\\/math\\\/event\\\/colloquium-dr-christine-cheng\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/uwm.edu\\\/math\\\/event\\\/colloquium-dr-christine-cheng\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/uwm.edu\\\/math\\\/event\\\/colloquium-dr-christine-cheng\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\",\"item\":\"https:\\\/\\\/uwm.edu\\\/math\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Events\",\"item\":\"https:\\\/\\\/uwm.edu\\\/math\\\/events\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Colloquia\",\"item\":\"https:\\\/\\\/uwm.edu\\\/math\\\/events\\\/category\\\/colloquia\\\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Colloquium: Dr. Christine Cheng\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/uwm.edu\\\/math\\\/#website\",\"url\":\"https:\\\/\\\/uwm.edu\\\/math\\\/\",\"name\":\"Mathematical Sciences\",\"description\":\"UW-Milwaukee\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/uwm.edu\\\/math\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Mathematical Sciences","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/uwm.edu\/math\/event\/colloquium-dr-christine-cheng\/","og_locale":"en_US","og_type":"article","og_title":"Colloquium: Dr. Christine Cheng","og_description":"Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings An instance of the Stable Roommates (SR) problem consists of 2n agents, each with a preference list that linearly orders the other agents. The &hellip;","og_url":"https:\/\/uwm.edu\/math\/event\/colloquium-dr-christine-cheng\/","og_site_name":"Mathematical Sciences","article_modified_time":"2026-09-24T19:21:13+00:00","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/uwm.edu\/math\/event\/colloquium-dr-christine-cheng\/","url":"https:\/\/uwm.edu\/math\/event\/colloquium-dr-christine-cheng\/","name":"Colloquium: Dr. Christine Cheng - Mathematical Sciences","isPartOf":{"@id":"https:\/\/uwm.edu\/math\/#website"},"datePublished":"2026-09-24T18:31:25+00:00","dateModified":"2026-09-24T19:21:13+00:00","breadcrumb":{"@id":"https:\/\/uwm.edu\/math\/event\/colloquium-dr-christine-cheng\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/uwm.edu\/math\/event\/colloquium-dr-christine-cheng\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/uwm.edu\/math\/event\/colloquium-dr-christine-cheng\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"","item":"https:\/\/uwm.edu\/math\/"},{"@type":"ListItem","position":2,"name":"Events","item":"https:\/\/uwm.edu\/math\/events\/"},{"@type":"ListItem","position":3,"name":"Colloquia","item":"https:\/\/uwm.edu\/math\/events\/category\/colloquia\/"},{"@type":"ListItem","position":4,"name":"Colloquium: Dr. Christine Cheng"}]},{"@type":"WebSite","@id":"https:\/\/uwm.edu\/math\/#website","url":"https:\/\/uwm.edu\/math\/","name":"Mathematical Sciences","description":"UW-Milwaukee","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/uwm.edu\/math\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/uwm.edu\/math\/wp-json\/wp\/v2\/tribe_events\/17083","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/uwm.edu\/math\/wp-json\/wp\/v2\/tribe_events"}],"about":[{"href":"https:\/\/uwm.edu\/math\/wp-json\/wp\/v2\/types\/tribe_events"}],"author":[{"embeddable":true,"href":"https:\/\/uwm.edu\/math\/wp-json\/wp\/v2\/users\/30596"}],"version-history":[{"count":1,"href":"https:\/\/uwm.edu\/math\/wp-json\/wp\/v2\/tribe_events\/17083\/revisions"}],"predecessor-version":[{"id":17084,"href":"https:\/\/uwm.edu\/math\/wp-json\/wp\/v2\/tribe_events\/17083\/revisions\/17084"}],"wp:attachment":[{"href":"https:\/\/uwm.edu\/math\/wp-json\/wp\/v2\/media?parent=17083"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/uwm.edu\/math\/wp-json\/wp\/v2\/tags?post=17083"},{"taxonomy":"tribe_events_cat","embeddable":true,"href":"https:\/\/uwm.edu\/math\/wp-json\/wp\/v2\/tribe_events_cat?post=17083"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}