main-content

## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

03.09.2020 | Ausgabe 4/2020

# Online maximum matching with recourse

Zeitschrift:
Journal of Combinatorial Optimization > Ausgabe 4/2020
Autoren:
Spyros Angelopoulos, Christoph Dürr, Shendan Jin
Wichtige Hinweise
Supported by ANR OATA (ANR-15-CE40-0015), DIM RFSI DACM and Labex Mathématique Hadamard. Preliminary version appeared in the Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), 2018.

## Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## 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. (Inf Process Lett 113(3):81–86, 2013), whereas the special case $$k=2$$ was studied by Boyar et al. (Proceedings of the 15th workshop on algorithms and data structures (WADS), pp 217–228, 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 of Avitabile et al., by exploiting the structure of the matching problem. In addition, we 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 L-Greedy, and we show that for small values of k it outperforms the algorithm AMP. In terms of lower bounds, we show that no deterministic algorithm better than $$1+1/(k-1)$$ exists, improving upon the known lower bound of $$1+1/k$$. 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 L-Greedy and AMP carry through in this model; moreover we show a lower bound of $$(k^2-3k+6) / (k^2-4k+7)$$ for all even $$k \ge 4$$. For $$k\in \{2,3\}$$, the competitive ratio is 3/2.

### Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

• über 69.000 Bücher
• über 500 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe
• Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 58.000 Bücher
• über 300 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

• über 50.000 Bücher
• über 380 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Zur Ausgabe