Dynamic Matching Algorithms in Practice

Monika Henzinger; Shahbaz Khan; Richard Paul; Christian Schulz

doi:10.4230/LIPIcs.ESA.2020.58

Dynamic Matching Algorithms in Practice

Monika Henzinger, Shahbaz Khan, Richard Paul, Christian Schulz

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

Abstrakti

In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances.

Alkuperäiskieli	englanti
Otsikko	28th Annual European Symposium on Algorithms (ESA 2020)
Toimittajat	Fabrizio Grandoni, Grzegorz Herman, Peter Sanders
Sivumäärä	20
Julkaisupaikka	Germany
Kustantaja	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Julkaisupäivä	8 syyskuuta 2020
ISBN (elektroninen)	978-3-95977-162-7
DOI - pysyväislinkit	https://doi.org/10.4230/LIPIcs.ESA.2020.58
Tila	Julkaistu - 8 syyskuuta 2020
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	Annual European Symposium on Algorithms - Online, Pisa, Italia Kesto: 7 syyskuuta 2020 → 10 syyskuuta 2020 Konferenssinumero: 28 http://algo2020.di.unipi.it/

Julkaisusarja

Nimi	Leibniz International Proceedings in Informatics (LIPIcs)
Vuosikerta	173
ISSN (painettu)	1868-8969

Tieteenalat

113 Tietojenkäsittely- ja informaatiotieteet

Pääsy asiakirjaan

10.4230/LIPIcs.ESA.2020.58Lisenssi: CC BY

LIPIcs-ESA-2020-58Lopullinen julkaistu versio, 1,06 MBLisenssi: CC BY

Siteeraa tätä

Henzinger, M., Khan, S., Paul, R., & Schulz, C. (2020). Dynamic Matching Algorithms in Practice. teoksessa F. Grandoni, G. Herman, & P. Sanders (Toimittajat), 28th Annual European Symposium on Algorithms (ESA 2020) (Leibniz International Proceedings in Informatics (LIPIcs); Vuosikerta 173). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2020.58

@inproceedings{dd264ed9d964446fb6039dcad0f1b92c,

title = "Dynamic Matching Algorithms in Practice",

abstract = " In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances. ",

keywords = "cs.DS, 113 Computer and information sciences",

author = "Monika Henzinger and Shahbaz Khan and Richard Paul and Christian Schulz",

year = "2020",

month = sep,

day = "8",

doi = "10.4230/LIPIcs.ESA.2020.58",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Fabrizio Grandoni and Herman, {Grzegorz } and { Sanders}, Peter",

booktitle = "28th Annual European Symposium on Algorithms (ESA 2020)",

address = "Germany",

note = "Annual European Symposium on Algorithms, ESA ; Conference date: 07-09-2020 Through 10-09-2020",

url = "http://algo2020.di.unipi.it/",

}

Henzinger, M, Khan, S, Paul, R & Schulz, C 2020, Dynamic Matching Algorithms in Practice. julkaisussa F Grandoni, G Herman & P Sanders (toim), 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Vuosikerta 173, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, Annual European Symposium on Algorithms, Pisa, Italia, 07/09/2020. https://doi.org/10.4230/LIPIcs.ESA.2020.58

Dynamic Matching Algorithms in Practice. / Henzinger, Monika; Khan, Shahbaz; Paul, Richard; Schulz, Christian.

28th Annual European Symposium on Algorithms (ESA 2020). toim. / Fabrizio Grandoni; Grzegorz Herman; Peter Sanders. Germany : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. (Leibniz International Proceedings in Informatics (LIPIcs); Vuosikerta 173).

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

TY - GEN

T1 - Dynamic Matching Algorithms in Practice

AU - Henzinger, Monika

AU - Khan, Shahbaz

AU - Paul, Richard

AU - Schulz, Christian

N1 - Conference code: 28

PY - 2020/9/8

Y1 - 2020/9/8

N2 - In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances.

AB - In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances.

KW - cs.DS

KW - 113 Computer and information sciences

U2 - 10.4230/LIPIcs.ESA.2020.58

DO - 10.4230/LIPIcs.ESA.2020.58

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 28th Annual European Symposium on Algorithms (ESA 2020)

A2 - Grandoni, Fabrizio

A2 - Herman, Grzegorz

A2 - Sanders, Peter

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Germany

T2 - Annual European Symposium on Algorithms

Y2 - 7 September 2020 through 10 September 2020

ER -