Angelopoulos, Spyros ;
Dürr, Christoph ;
Jin, Shendan
Online Maximum Matching with Recourse
Abstract
We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter k. An online algorithm for this problem has to maintain a valid matching while edges of the underlying graph are presented one after the other. At any moment the algorithm can decide to include an edge into the matching or to exclude it, under the restriction that at most k such actions per edge take place, where k is typically a small constant. This problem was introduced and studied in the context of general online packing problems with recourse by Avitabile et al. [Avitabile et al., 2013], whereas the special case k=2 was studied by Boyar et al. [Boyar et al., 2017].
In the first part of this paper, we consider the edge arrival model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP given in [Avitabile et al., 2013], by exploiting the structure of the matching problem. In addition, we extend the result of [Boyar et al., 2017] and show that the greedy algorithm has competitive ratio 3/2 for every even k and ratio 2 for every odd k. Moreover, we present and analyze an improvement of the greedy algorithm which we call LGreedy, and we show that for small values of k it outperforms the algorithm of [Avitabile et al., 2013]. In terms of lower bounds, we show that no deterministic algorithm better than 1+1/(k1) exists, improving upon the lower bound of 1+1/k shown in [Avitabile et al., 2013].
The second part of the paper is devoted to the edge arrival/departure model, which is the fully dynamic variant of online matching with recourse. The analysis of LGreedy and AMP carry through in this model; moreover we show a lower bound of (k^23k+6)/(k^24k+7) for all even k >= 4. For k in {2,3}, the competitive ratio is 3/2.
BibTeX  Entry
@InProceedings{angelopoulos_et_al:LIPIcs:2018:9590,
author = {Spyros Angelopoulos and Christoph D{\"u}rr and Shendan Jin},
title = {{Online Maximum Matching with Recourse}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {8:18:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9590},
URN = {urn:nbn:de:0030drops95908},
doi = {10.4230/LIPIcs.MFCS.2018.8},
annote = {Keywords: Competitive ratio, maximum cardinality matching, recourse}
}
27.08.2018
Keywords: 

Competitive ratio, maximum cardinality matching, recourse 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

27.08.2018 