Online maximum matching with recourse

摘要: We study the online maximum matching problem in a model which edges are associated with known recourse parameter k. An algorithm for this has to maintain valid while of underlying graph presented one after other. At any moment can decide include an edge into or exclude it, under restriction that at most k such actions per take place, where is typically small constant. This was introduced and studied context general packing problems by Avitabile et al. (Inf Process Lett 113(3):81–86, 2013), whereas special case $$k=2$$ Boyar (Proceedings 15th workshop on algorithms data structures (WADS), pp 217–228, 2017). In first part paper we consider arrival model, arriving never disappears from graph. Here, show improved analysis performance AMP al., exploiting structure problem. addition, greedy competitive ratio 3/2 every even 2 odd Moreover, present analyze improvement call L-Greedy, values it outperforms AMP. terms lower bounds, no deterministic better than $$1+1/(k-1)$$ exists, improving upon bound $$1+1/k$$ . The second devoted arrival/departure fully dynamic variant recourse. L-Greedy carry through model; moreover $$(k^2-3k+6) / (k^2-4k+7)$$ all $$k \ge 4$$ . For $$k\in \{2,3\}$$ , 3/2.