{"id":{"repo_id":"clemson","oai_identifier":"oai:open.clemson.edu:all_theses-1193"},"canonical_url":"https://search.ndltd.org/etd/clemson/oai:open.clemson.edu:all_theses-1193","repository":{"repo_id":"clemson","name":"Clemson University","base_url":"https://open.clemson.edu/do/oai/"},"display":{"title":"FASTER ALGORITHMS FOR STABLE ALLOCATION PROBLEMS","abstract":"We consider a high-multiplicity generalization of the classical stable matching problem known as the stable allocation problem, introduced by Baiou and Balinski in 2002. By leveraging new structural properties and sophisticated data structures, we show how to solve this problem in O(mlog n) time on an bipartite instance with n nodes and m edges, improving the best known running time of O(mn). Our approach simplifies the algorithmic landscape for this problem by providing a common generalization of two different approaches from the literature -- the classical Gale-Shapley algorithm, and a recent algorithm of Baiou and Balinski. Building on this algorithm, we provide an O(m log n) algorithm for the non-bipartite stable allocation problem that introduces a new and useful transformation from non-bipartite to bipartite instances. We also give a polynomial-time algorithm for solving the 'optimal' variant of the bipartite stable allocation problem, as well as a 2-approximation algorithm for the NP-hard 'optimal' variant of the non-bipartite stable allocation problem. Finally, we highlight some important connections between the stable allocation problem and the maximum flow problem.","abstract_html":"We consider a high-multiplicity generalization of the classical stable matching problem known as the stable allocation problem, introduced by Baiou and Balinski in 2002. By leveraging new structural properties and sophisticated data structures, we show how to solve this problem in O(mlog n) time on an bipartite instance with n nodes and m edges, improving the best known running time of O(mn). Our approach simplifies the algorithmic landscape for this problem by providing a common generalization of two different approaches from the literature -- the classical Gale-Shapley algorithm, and a recent algorithm of Baiou and Balinski. Building on this algorithm, we provide an O(m log n) algorithm for the non-bipartite stable allocation problem that introduces a new and useful transformation from non-bipartite to bipartite instances. We also give a polynomial-time algorithm for solving the &#x27;optimal&#x27; variant of the bipartite stable allocation problem, as well as a 2-approximation algorithm for the NP-hard &#x27;optimal&#x27; variant of the non-bipartite stable allocation problem. Finally, we highlight some important connections between the stable allocation problem and the maximum flow problem.","abstract_has_math":false,"creators":["Munshi, Siddharth"],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Dean, Brian","Jacobs , David","Wang , James"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:06:13Z","subjects":["stable","marriage","allocation","bipartite","optimal","matching","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://open.clemson.edu/all_theses/193","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://open.clemson.edu/all_theses/193","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://open.clemson.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Aopen.clemson.edu%3Aall_theses-1193","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Dean, Brian","Jacobs , David","Wang , James"]},{"key":"dc:creator","label":"Author","values":["Munshi, Siddharth"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2015-09-30T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2007-08-25T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["stable","marriage","allocation","bipartite","optimal","matching","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://open.clemson.edu/all_theses/193"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["We consider a high-multiplicity generalization of the classical stable matching problem known as the stable allocation problem, introduced by Baiou and Balinski in 2002. By leveraging new structural properties and sophisticated data structures, we show how to solve this problem in O(mlog n) time on an bipartite instance with n nodes and m edges, improving the best known running time of O(mn). Our approach simplifies the algorithmic landscape for this problem by providing a common generalization of two different approaches from the literature -- the classical Gale-Shapley algorithm, and a recent algorithm of Baiou and Balinski. Building on this algorithm, we provide an O(m log n) algorithm for the non-bipartite stable allocation problem that introduces a new and useful transformation from non-bipartite to bipartite instances. We also give a polynomial-time algorithm for solving the 'optimal' variant of the bipartite stable allocation problem, as well as a 2-approximation algorithm for the NP-hard 'optimal' variant of the non-bipartite stable allocation problem. Finally, we highlight some important connections between the stable allocation problem and the maximum flow problem."]},{"key":"dc:title","label":"Title","values":["FASTER ALGORITHMS FOR STABLE ALLOCATION PROBLEMS"]}]}],"canonical_facts":{"dc:contributor":["Dean, Brian","Jacobs , David","Wang , James"],"dc:creator":["Munshi, Siddharth"],"dc:date.available":["2015-09-30T07:00:00Z"],"dc:date.created":["2007-08-25T07:00:00Z"],"dc:description.abstract":["We consider a high-multiplicity generalization of the classical stable matching problem known as the stable allocation problem, introduced by Baiou and Balinski in 2002. By leveraging new structural properties and sophisticated data structures, we show how to solve this problem in O(mlog n) time on an bipartite instance with n nodes and m edges, improving the best known running time of O(mn). Our approach simplifies the algorithmic landscape for this problem by providing a common generalization of two different approaches from the literature -- the classical Gale-Shapley algorithm, and a recent algorithm of Baiou and Balinski. Building on this algorithm, we provide an O(m log n) algorithm for the non-bipartite stable allocation problem that introduces a new and useful transformation from non-bipartite to bipartite instances. We also give a polynomial-time algorithm for solving the 'optimal' variant of the bipartite stable allocation problem, as well as a 2-approximation algorithm for the NP-hard 'optimal' variant of the non-bipartite stable allocation problem. Finally, we highlight some important connections between the stable allocation problem and the maximum flow problem."],"dc:identifier":["https://open.clemson.edu/all_theses/193"],"dc:subject":["stable","marriage","allocation","bipartite","optimal","matching","Computer Sciences"],"dc:title":["FASTER ALGORITHMS FOR STABLE ALLOCATION PROBLEMS"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T07:06:13Z"}