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