Room allocation with capacity diversity and budget constraints
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...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/106248 http://hdl.handle.net/10220/48923 http://dx.doi.org/10.1109/ACCESS.2019.2907708 |
| _version_ | 1811683206920929280 |
|---|---|
| author | Li, Yunpeng Jiang, Yichuan Wu, Weiwei Jiang, Jiuchuan Fan, Hui |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Li, Yunpeng Jiang, Yichuan Wu, Weiwei Jiang, Jiuchuan Fan, Hui |
| author_sort | Li, Yunpeng |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T04:09:03Z |
| format | Journal Article |
| id | ntu-10356/106248 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:09:03Z |
| publishDate | 2019 |
| record_format | dspace |
| spelling | ntu-10356/1062482019-12-06T22:07:22Z Room allocation with capacity diversity and budget constraints Li, Yunpeng Jiang, Yichuan Wu, Weiwei Jiang, Jiuchuan Fan, Hui School of Computer Science and Engineering DRNTU::Engineering::Computer science and engineering Room Allocation Capacity Diversity 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. Published version 2019-06-24T06:48:40Z 2019-12-06T22:07:22Z 2019-06-24T06:48:40Z 2019-12-06T22:07:22Z 2019 Journal Article 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 https://hdl.handle.net/10356/106248 http://hdl.handle.net/10220/48923 http://dx.doi.org/10.1109/ACCESS.2019.2907708 en IEEE Access © 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. 19 p. application/pdf |
| spellingShingle | DRNTU::Engineering::Computer science and engineering Room Allocation Capacity Diversity Li, Yunpeng Jiang, Yichuan Wu, Weiwei Jiang, Jiuchuan Fan, Hui Room allocation with capacity diversity and budget constraints |
| title | Room allocation with capacity diversity and budget constraints |
| title_full | Room allocation with capacity diversity and budget constraints |
| title_fullStr | Room allocation with capacity diversity and budget constraints |
| title_full_unstemmed | Room allocation with capacity diversity and budget constraints |
| title_short | Room allocation with capacity diversity and budget constraints |
| title_sort | room allocation with capacity diversity and budget constraints |
| topic | DRNTU::Engineering::Computer science and engineering Room Allocation Capacity Diversity |
| url | https://hdl.handle.net/10356/106248 http://hdl.handle.net/10220/48923 http://dx.doi.org/10.1109/ACCESS.2019.2907708 |
| work_keys_str_mv | AT liyunpeng roomallocationwithcapacitydiversityandbudgetconstraints AT jiangyichuan roomallocationwithcapacitydiversityandbudgetconstraints AT wuweiwei roomallocationwithcapacitydiversityandbudgetconstraints AT jiangjiuchuan roomallocationwithcapacitydiversityandbudgetconstraints AT fanhui roomallocationwithcapacitydiversityandbudgetconstraints |