Online Maximum Matching with Recourse

摘要: We study the online maximum matching problem with recourse in a model which edges are associated known 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$ actions per take place, where is typically small constant. This was introduced and studied context general packing problems by [Avitabile, Mathieu, Parkinson, 2013], whereas special case $k=2$ been [Boyar et al., 2017]. In first part paper, we consider arrival model, arriving never disappears from graph. Here, show improved analysis on performance given [AMP, exploiting structure specific problem. In addition, extend result 2017] greedy ratio $3/2$ every even positive $2$ odd Moreover, present analyze $L$-Greedy --- improvement values outperforms 2013]. terms lower bounds, no deterministic better than $1+1/(k-1)$ exists, improving upon bound $1+1/k$ shown The second paper devoted arrival/departure fully dynamic variant recourse. The carries through model; moreover $(k^2-3k+3)/(k^2-4k+5)$ all $k \ge 4$ provide stronger $10/7$ $k=4$. For $k\in\{2,3\}$, competitive $3/2$.