English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the online bipartite matching with reassignments problem, an algorithm isinitially given only one side of the vertex set of a bipartite graph; thevertices on the other side are revealed to the algorithm one by one, along withits incident edges. The algorithm is required to maintain a matching in thecurrent graph, where the algorithm revises the matching after each vertexarrival by reassigning vertices. Bernstein, Holm, and Rotenberg showed that anonline algorithm can maintain a matching of maximum cardinality by performingamortized $O(\log^2 n)$ reassignments per arrival.  In this paper, we propose to consider the general question of how requiring anon-amortized hard budget $k$ on the number of reassignments affects thealgorithms' performances, under various models from the literature.  We show that a simple, widely-used algorithm is a best-possible deterministicalgorithm for all these models. For the unweighted maximum-cardinality problem,the algorithm is a $(1-\frac{2}{k+2})$-competitive algorithm, which is the bestpossible for a deterministic algorithm both under vertex arrivals and edgearrivals. Applied to the load balancing problem, this yields a bifactor onlinealgorithm. For the weighted problem, which is traditionally studied assumingthe triangle inequality, we show that the power of reassignment allows us tolift this assumption and the algorithm becomes a $\frac{1}{2}$-competitivealgorithm for $k=4$, improving upon the $\frac{1}{3}$ of the previous algorithmwithout reassignments. We show that this also is a best-possible deterministicalgorithm.

Online Graph Matching Problems with a Worst-Case Reassignment Budget