Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями

Две пары черных ребер называются пересекающимися, если они чередуются в порядке их появления в круге. Пара черных ребер пересекается с циклом C, если она пересекается в парой черных ребер, принадлежащих к C. Циклы C и D пересекаются, если существует пара черных ребер в C, которая пересекается с D (см. рис. 2e). Два пересекающихся цикла называются перемежающимися, если их пары черных чередуются в порядке их появления в круге (см. рис. 2f). Очевидно, что два цикла могут находиться друг с другом в одном из следующих отношений: (1) непересекающиеся, (2) пересекающиеся, но не перемежающиеся, (3) перемежающиеся. Пара черных ребер называется связанной, если эти ребра соединены серым ребром и если при чтении ребер вдоль цикла они читаются в одном и том же направлении. К примеру, на рис. 2a все пары черных ребер являются связанными. Гу и др. [ ] показали, что для пары связанных черных ребер (b1, b2) существует цикл С, пересекающийся с (b1, b2). 1-скрученной парой является пара 1-скрученных циклов, повороты которых являются последовательными на круге в конфигурации, состоящей только из этих двух циклов. 1-скрученный цикл называется закрытым в конфигурации, если два его связанных ребра пересекаются с некоторым другим циклом конфигурации. Конфигурация называется закрытой, если по крайней мере один из ее 1-скрученных циклов является закрытым; в противном случае она называется открытой.

Теорема 1. Задача сортировки линейных перестановок при помощи транспозиций, транспозиций-обращений и двойных обращений является линейно эквивалентной задаче сортировки циклических перестановок при помощи транспозиций, транспозиций-обращений и двойных обращений.

Теорема 2. Существует алгоритм 1,5-аппроксимации для сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, выполняющийся за время <math>O(n^{3/2} \sqrt{log \; n})</math>.