Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/106248
Title: Room allocation with capacity diversity and budget constraints
Authors: Li, Yunpeng
Jiang, Yichuan
Wu, Weiwei
Jiang, Jiuchuan
Fan, Hui
Keywords: DRNTU::Engineering::Computer science and engineering
Room Allocation
Capacity Diversity
Issue Date: 2019
Source: Li, 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.2907708
Series/Report no.: IEEE Access
Abstract: With 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.
URI: https://hdl.handle.net/10356/106248
http://hdl.handle.net/10220/48923
DOI: 10.1109/ACCESS.2019.2907708
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 http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
Fulltext Permission: open
Fulltext Availability: With 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
View/Open

SCOPUSTM   
Citations

1
checked on Jul 16, 2020

WEB OF SCIENCETM
Citations

1
checked on Oct 23, 2020

Page view(s)

97
checked on Oct 28, 2020

Download(s)

24
checked on Oct 28, 2020

Google ScholarTM

Check

Altmetric


Plumx

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