Deferred on-line bipartite matching
type: Item
instance of: scholarly article
title: Deferred on-line bipartite matching
zbMATH Open document ID: 1457.68317
author: Jakub Kozik
author: Grzegorz Matecki
published in: The Electronic Journal of Combinatorics
publication date: 2018-05-25T00:00:00Z
full work available at URL: v25i2p24
review text: Summary: We present a new model for the problem of on-line matching on bipartite graphs. Suppose that one part of a graph is given, but the vertices of the other part are presented in an on-line fashion. In the classical version, each incoming vertex is either irrevocably matched to a vertex from the other part or stays unmatched forever. In our version, an algorithm is allowed to match the new vertex to a group of elements (possibly empty). Later on, the algorithm can decide to remove some vertices from the group and assign them to another (just presented) vertex, with the restriction that each element belongs to at most one group. We present an optimal (deterministic) algorithm for this problem and prove that its competitive ratio equals \(1-\pi/\cosh(\frac{\sqrt{3}}{2}\pi)\approx 0.588\).
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6873183
zbMATH Keywords: online bipartite matching
zbMATH Keywords: adaptive algorithm
MaRDI profile type: Publication
cites work: Optimal Node Routing
cites work: The Competitiveness of On-Line Assignments
cites work: Management of multi-queue switches in QoS networks
cites work: Improved Bounds for Online Stochastic Matching
cites work: On-line chain partitions of orders: a survey
cites work: On Randomized Algorithms for Matching in the Online Preemptive Model
description: scientific article; zbMATH DE number 6873183