Geodesic
Improved first player strategy for the zero-sum sequential uncrossing game
Ural mathematical journal, Tome 10 (2024) no. 1, pp. 136-146 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This paper deals with the known uncrossing zero-sum two-player sequential game, which is employed to obtain upper running time bound for the transformation of an arbitrary subset family of some finite set to an appropriate laminar one. In this game, the first player performs such a transformation, while the second one tries to slow down this process as much as possible. It is known that for any game instance specified by the ground set and initial subset family of size $n$ and $m$ respectively, the first player has a winning strategy of $O(n^4m)$ steps. In this paper, we show that the first player has a more efficient strategy, which helps him (her) to win in $O\bigl(\max\{n^2,mn\}\bigr)$ steps.
Keywords: Laminar family, Uncrossing game, Efficient winning strategy 
@article{UMJ_2024_10_1_a11,
     author = {Ksenia Rizhenko},
     title = {Improved first player strategy for the zero-sum sequential uncrossing game},
     journal = {Ural mathematical journal},
     pages = {136--146},
     year = {2024},
     volume = {10},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UMJ_2024_10_1_a11/}
}
TY  - JOUR
AU  - Ksenia Rizhenko
TI  - Improved first player strategy for the zero-sum sequential uncrossing game
JO  - Ural mathematical journal
PY  - 2024
SP  - 136
EP  - 146
VL  - 10
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/UMJ_2024_10_1_a11/
LA  - en
ID  - UMJ_2024_10_1_a11
ER  - 
%0 Journal Article
%A Ksenia Rizhenko
%T Improved first player strategy for the zero-sum sequential uncrossing game
%J Ural mathematical journal
%D 2024
%P 136-146
%V 10
%N 1
%U http://geodesic.mathdoc.fr/item/UMJ_2024_10_1_a11/
%G en
%F UMJ_2024_10_1_a11
Ksenia Rizhenko. Improved first player strategy for the zero-sum sequential uncrossing game. Ural mathematical journal, Tome 10 (2024) no. 1, pp. 136-146. http://geodesic.mathdoc.fr/item/UMJ_2024_10_1_a11/

[1] Cecchetto F., Traub V., Zenklusen R., “Better-than-${4}/{3}$-approximations for leaf-to-leaf tree and connectivity augmentation”, Math. Program., 2023, 1–23 | DOI | MR

[2] Karzanov A. V., “How to tidy up a symmetric set-system by use of uncrossing operations”, Theor. Comput. Sci., 157:2 (1996), 215–225 | DOI | MR | Zbl

[3] Khachay M.Yu., Neznakhina E.D., Ryzhenko K.V., “Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem”, Proc. Steklov Inst. Math., 319:Suppl. 1 (2022), S140–S155 | DOI | MR | Zbl

[4] Kortsarz G., Nutov Z., “{LP}-relaxations for tree augmentation”, Discr. Appl. Math., 239 (2018), 94–105 | DOI | MR | Zbl

[5] Maduel Y., Nutov Z., “Covering a laminar family by leaf to leaf links”, Discr. Appl. Math., 158:13 (2010), 1424–1432 | DOI | MR | Zbl

[6] Neznakhina E. D., Ogorodnikov Yu. Yu., Rizhenko K. V., Khachay M. Yu., “Approximation algorithms with constant factors for a series of asymmetric routing problems”, Dokl. Math., 108:3 (2023), 499–505 | DOI | MR

[7] Rizhenko K., Neznakhina K., Khachay M., “Fixed ratio polynomial time approximation algorithm for the prize-collecting asymmentric traveling salesman problem”, Ural Math. J., 9:1 (2023), 135–146 | DOI | MR

[8] Schrijver A., Combinatorial Optimization. Polyhedra and Efficiency, Springer, Berlin, Heidelberg, 2003, 1879 pp. https://link.springer.com/book/9783540443896 | MR | Zbl

[9] Svensson O., Tarnawski J., Végh L., “A constant-factor approximation algorithm for the asymmetric traveling salesman problem”, J. ACM., 67:6 (2020), 37, 1–53 | DOI | MR

[10] Traub V., Vygen J., “An improved approximation algorithm for the asymmetric traveling salesman problem”, SIAM J. on Comput., 51:1 (2022), 139–173 | DOI | MR | Zbl