Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLi, Yunpengen
dc.contributor.authorJiang, Yichuanen
dc.contributor.authorWu, Weiweien
dc.contributor.authorJiang, Jiuchuanen
dc.contributor.authorFan, Huien
dc.identifier.citationLi, Y., Jiang, Y., Wu, W., Jiang, J., & Fan, H. (2019). Room allocation with capacity diversity and budget constraints. IEEE Access, 7, 42968-42986. doi:10.1109/ACCESS.2019.2907708en
dc.description.abstractWith the development of the room rental market, many room rental websites have been created, e.g., SpareRoom and EasyRoommate. On these websites, people find not only rooms for rent but also suitable roommates. Inspired by the rental mode in practice, a benchmark room allocation model was introduced by Chan et al., in which 2n agents must be allocated to n rooms that have the same capacity and each agent can be allocated to any room. However, in practice, rooms may differ in terms of capacity, e.g., college dorms or apartments may contain both two-bed rooms and four-bed rooms. Moreover, an agent can only be allocated to a room of which the rent does not exceed the agent's budget. In this scenario, we must consider not only the agents' preferences but also the capacity diversity of the rooms and the budget constraints while allocating the rooms. Therefore, this paper investigates the room allocation problem with capacity diversity and budget constraints. We mainly focus on finding an allocation that maximizes social welfare. First, this paper demonstrates that finding an allocation that maximizes the social welfare is NP-hard (i.e., non-deterministic polynomial-time hard), even if only one room's capacity is larger than 1 and the other rooms' capacities are all 1. Second, this paper presents a (c* + 2)/2 + ε-factor approximation algorithm (with ε > 0) for the case in which the capacity of each room does not exceed a constant c*. Third, this paper proposes a heuristic algorithm based on the local search for the general case in which the capacity of each room is not bounded by a constant. The experimental results demonstrate that the proposed algorithm can produce near-optimal solutions. Finally, this paper investigates how to find a roommate stable or room envyfree allocation with a social welfare guarantee.en
dc.format.extent19 p.en
dc.relation.ispartofseriesIEEE Accessen
dc.rights© 2019 IEEE. Translations and content mining are permitted for academic research only. Personal use is also permitted, but republication/redistribution requires IEEE permission. See for more information.en
dc.subjectDRNTU::Engineering::Computer science and engineeringen
dc.subjectRoom Allocationen
dc.subjectCapacity Diversityen
dc.titleRoom allocation with capacity diversity and budget constraintsen
dc.typeJournal Articleen
dc.contributor.schoolSchool of Computer Science and Engineeringen
dc.description.versionPublished versionen
item.fulltextWith Fulltext-
Appears in Collections:SCSE Journal Articles
Files in This Item:
File Description SizeFormat 
Room allocation with capacity diversity and budget constraints.pdf3.94 MBAdobe PDFThumbnail

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.