Shortest augmenting paths for online matchings on trees

2018
journal article
article
4
cris.lastimport.wos2024-04-09T20:16:48Z
dc.abstract.enThe shortest augmenting path (Sap) algorithm is one of the most classical approaches to the maximum matching and maximum flow problems, e.g., using it Edmonds and Karp (J. ACM 19(2), 248–264 1972) have shown the first strongly polynomial time algorithm for the maximum flow problem. Quite astonishingly, although it has been studied for many years already, this approach is far from being fully understood. This is exemplified by the online bipartite matching problem. In this problem a bipartite graph G = (W ⊎ B, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. After arrival of this vertex we augment the current matching by using shortest augmenting path. It was conjectured by Chaudhuri et al. (INFOCOM’09) that the total length of all augmenting paths found by Sap is O(nlogn). However, no better bound than O(n2) is known even for trees. In this paper we prove an O(nlog2n) upper bound for the total length of augmenting paths for trees.pl
dc.affiliationWydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznejpl
dc.contributor.authorBosek, Bartłomiej - 114402 pl
dc.contributor.authorLeniowski, Dariuszpl
dc.contributor.authorSankowski, Piotrpl
dc.contributor.authorZych-Pawlewicz, Annapl
dc.date.accessioned2018-03-09T10:00:41Z
dc.date.available2018-03-09T10:00:41Z
dc.date.issued2018pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number2pl
dc.description.physical337-348pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume62pl
dc.identifier.doi10.1007/s00224-017-9838-xpl
dc.identifier.eissn1433-0490pl
dc.identifier.issn1432-4350pl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/51539
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa 3.0 Polska*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/pl/legalcode*
dc.share.typeinne
dc.subject.enonline matchingspl
dc.subject.enbipartite matchingspl
dc.subject.enapproximate matchingspl
dc.subject.enshortest augmenting pathspl
dc.subject.endynamic graph algorithmspl
dc.subtypeArticlepl
dc.titleShortest augmenting paths for online matchings on treespl
dc.title.journalTheory of Computing Systemspl
dc.typeJournalArticlepl
dspace.entity.typePublication
cris.lastimport.wos
2024-04-09T20:16:48Z
dc.abstract.enpl
The shortest augmenting path (Sap) algorithm is one of the most classical approaches to the maximum matching and maximum flow problems, e.g., using it Edmonds and Karp (J. ACM 19(2), 248–264 1972) have shown the first strongly polynomial time algorithm for the maximum flow problem. Quite astonishingly, although it has been studied for many years already, this approach is far from being fully understood. This is exemplified by the online bipartite matching problem. In this problem a bipartite graph G = (W ⊎ B, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. After arrival of this vertex we augment the current matching by using shortest augmenting path. It was conjectured by Chaudhuri et al. (INFOCOM’09) that the total length of all augmenting paths found by Sap is O(nlogn). However, no better bound than O(n2) is known even for trees. In this paper we prove an O(nlog2n) upper bound for the total length of augmenting paths for trees.
dc.affiliationpl
Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej
dc.contributor.authorpl
Bosek, Bartłomiej - 114402
dc.contributor.authorpl
Leniowski, Dariusz
dc.contributor.authorpl
Sankowski, Piotr
dc.contributor.authorpl
Zych-Pawlewicz, Anna
dc.date.accessioned
2018-03-09T10:00:41Z
dc.date.available
2018-03-09T10:00:41Z
dc.date.issuedpl
2018
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.numberpl
2
dc.description.physicalpl
337-348
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
62
dc.identifier.doipl
10.1007/s00224-017-9838-x
dc.identifier.eissnpl
1433-0490
dc.identifier.issnpl
1432-4350
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/51539
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights*
Udzielam licencji. Uznanie autorstwa 3.0 Polska
dc.rights.licence
CC-BY
dc.rights.uri*
http://creativecommons.org/licenses/by/3.0/pl/legalcode
dc.share.type
inne
dc.subject.enpl
online matchings
dc.subject.enpl
bipartite matchings
dc.subject.enpl
approximate matchings
dc.subject.enpl
shortest augmenting paths
dc.subject.enpl
dynamic graph algorithms
dc.subtypepl
Article
dc.titlepl
Shortest augmenting paths for online matchings on trees
dc.title.journalpl
Theory of Computing Systems
dc.typepl
JournalArticle
dspace.entity.type
Publication

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
1
Views per month
Downloads
bosek_leniowski_sankowski_zych-pawlewicz_shortest_augmenting_paths_for_online_matchings_2018.pdf
5