资源论文Online Roommate Allocation Problem?

Online Roommate Allocation Problem?

2019-10-29 | |  41 |   46 |   0
Abstract We study the online allocation problem under a roommate market model introduced in [Chan et al., 2016]. Consider a fixed supply of n rooms and a list of 2n applicants arriving online in random order. The problem is to assign a room to each person upon her arrival, such that after the algorithm terminates, each room is shared by exactly two people. We focus on two objectives: (1) maximizing the social welfare, which is defined as the sum of valuations that applicants have for their rooms, plus the happiness value between each pair of roommates; (2) satisfying the stability property that no small group of people would be willing to switch roommates or rooms. We first show a polynomial-time online algorithm that achieves a constant competitive ratio for social welfare maximization. We then extend it to the case where each room is assigned to c > 2 people, and achieve a competitive ratio of ?(1/c2). Finally, we show both positive and negative results in satisfying various stability conditions in this online setting

上一篇:On the Expressivity of Inconsistency Measures (Extended Abstract)?

下一篇:Open-World Probabilistic Databases: An Abridged Report

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...