Most prior work on online matching problems has been with the flexibility of keeping some vertices unmatched. We study three related online matching problems with the constraint of matching every vertex, i.e., with no rejections. We adopt a model in which vertices arrive in uniformly random order and the non-negative edge-weights are arbitrary. For the capacitated online bipartite matching problem, in which the vertices of one side of the graph are offline and those of the other side arrive online, we give a 4.62-competitive algorithm when the capacity of each offline vertex is 2. For the online general (non-bipartite) matching problem, where all vertices arrive online, we give a 3.34-competitive algorithm. We also study the online roommate matching problem (Huzhang et al. 2017), in which each room (offline vertex) holds 2 persons (online vertices). Persons derive non-negative additive utilities from their room as well as roommate. In this model, with the goal of maximizing the social welfare, we give a 7.96-competitive algorithm. This is an improvement over the 24.72 approximation factor in (Huzhang et al. 2017).
翻译:在网上匹配问题上,大多数先前的工作都是保持一些脊椎不相配的灵活性。 我们研究三个相关的在线匹配问题, 限制匹配每个脊椎, 即没有拒绝。 我们采用一个模式, 使脊椎以统一的随机顺序到达, 非负边边重量是任意的。 对于具有功能的在线双边匹配问题, 使图的一方的脊椎离线, 而另一方的脊椎进入在线, 我们给出一个4.62的竞争性算法, 当每个离线脊椎的容量为2. 时, 我们给出一个4.62的竞争性算法, 对于所有脊椎都在线到达的在线( 非双边)匹配问题, 我们给出一个3.34的竞争性算法。 我们还研究在线室友匹配问题( Huzhang et al. 2017), 每个房间( offline 脊椎) 都有2人( 在线脊椎 ) 。 人们从自己的房间和室室室室获得非负性添加功能。 在这种模型中, 为了最大限度地增加社会福利, 我们给出了7.762 和201717年的顶压。