{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:37Z","timestamp":1753893817059,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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.\u00a0In the classical version, each incoming vertex is either irrevocably matched to a vertex from the other part or stays unmatched forever.\u00a0In our version, an algorithm is allowed to match the new vertex to a group of elements (possibly empty).\u00a0Later on, the algorithm can decide to remove some vertices from the group and assign them to another (just presented) vertex,\u00a0with the restriction that each element belongs to at most one group.\u00a0We present an optimal (deterministic) algorithm for this problem and prove that its competitive ratio equals $1-\\pi\/\\cosh(\\frac{\\sqrt{3}}{2}\\pi)\\approx 0.588$.<\/jats:p>","DOI":"10.37236\/5756","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T15:33:42Z","timestamp":1578670422000},"source":"Crossref","is-referenced-by-count":0,"title":["Deferred On-Line Bipartite Matching"],"prefix":"10.37236","volume":"25","author":[{"given":"Jakub","family":"Kozik","sequence":"first","affiliation":[]},{"given":"Grzegorz","family":"Matecki","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2018,5,11]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v25i2p24\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v25i2p24\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T04:34:02Z","timestamp":1579235642000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v25i2p24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,11]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2018,4,13]]}},"URL":"https:\/\/doi.org\/10.37236\/5756","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2018,5,11]]},"article-number":"P2.24"}}