Simple view
Full metadata view
Authors
Statistics
Deferred on-line bipartite matching
on-line
bipartite matching
adaptive algorithm
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.
dc.abstract.en | 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. | pl |
dc.affiliation | Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej | pl |
dc.contributor.author | Kozik, Jakub - 129355 | pl |
dc.contributor.author | Matecki, Grzegorz - 130386 | pl |
dc.date.accession | 2018-05-11 | pl |
dc.date.accessioned | 2018-05-15T11:28:44Z | |
dc.date.available | 2018-05-15T11:28:44Z | |
dc.date.issued | 2018 | pl |
dc.date.openaccess | 0 | |
dc.description.accesstime | w momencie opublikowania | |
dc.description.number | 2 | pl |
dc.description.version | ostateczna wersja wydawcy | |
dc.description.volume | 25 | pl |
dc.identifier.articleid | P2.24 | pl |
dc.identifier.eissn | 1077-8926 | pl |
dc.identifier.issn | 1097-1440 | pl |
dc.identifier.project | UMO-2011/03/D/ST6/01370 | pl |
dc.identifier.project | 2011/03/B/ST6/01367 | pl |
dc.identifier.project | ROD UJ / P | pl |
dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/54311 | |
dc.identifier.weblink | http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p24 | pl |
dc.language | eng | pl |
dc.language.container | eng | pl |
dc.rights | Udzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa | * |
dc.rights.licence | CC-BY-ND | |
dc.rights.uri | http://creativecommons.org/licenses/by-nd/4.0/legalcode.pl | * |
dc.share.type | otwarte czasopismo | |
dc.subject.en | on-line | pl |
dc.subject.en | bipartite matching | pl |
dc.subject.en | adaptive algorithm | pl |
dc.subtype | Article | pl |
dc.title | Deferred on-line bipartite matching | pl |
dc.title.journal | The Electronic Journal of Combinatorics | pl |
dc.type | JournalArticle | pl |
dspace.entity.type | Publication |
* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.
Views
0
Views per month
Open Access