CHARACTERIZE WEAK AND SUPER STABILITY OF THE ROOMMATE PROBLEM UNDER WEAK PREFERENCES

Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/249424

DC Field	Value
dc.title	CHARACTERIZE WEAK AND SUPER STABILITY OF THE ROOMMATE PROBLEM UNDER WEAK PREFERENCES
dc.contributor.author	YU BIN
dc.date.accessioned	2024-08-13T02:30:58Z
dc.date.available	2024-08-13T02:30:58Z
dc.date.issued	2024-03-20
dc.identifier.citation	YU BIN (2024-03-20). CHARACTERIZE WEAK AND SUPER STABILITY OF THE ROOMMATE PROBLEM UNDER WEAK PREFERENCES. ScholarBank@NUS Repository.
dc.identifier.uri	https://scholarbank.nus.edu.sg/handle/10635/249424
dc.description.abstract	This paper presents a new structure called the "weak-stable partition" and "super-stable partition" which characterizes the weak and super stability of the roommate problem under weak preferences and extends the no-odd ring condition of stable roommate matching established in \cite{chung2000existence}. We demonstrate that finding such a stable partition under weak stability conditions is an NP-complete problem. Finding a stable partition under super stability condition admits polynomial algorithm.
dc.language.iso	en
dc.subject	stable roommate matching, stable partition, computation complexity
dc.type	Thesis
dc.contributor.department	INST OF OPERATIONS RESEARCH & ANALYTICS
dc.contributor.supervisor	Jussi Samuli Keppo
dc.description.degree	Master's
dc.description.degreeconferred	MASTER OF SCIENCE (RSH-IORA)
dc.identifier.orcid	0009-0003-8395-3623
Appears in Collections:	Master's Theses (Open)

File	Description	Size	Format	Access Settings	Version
YB.pdf		443.21 kB	Adobe PDF	OPEN	None	View/Download

Check