\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}

\def\udcs{519.168 519.712.3} %Здесь автор определяет УДК своей работы
\def\mscs{90C27 05C85 68W25} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{1}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}
\newtheorem{note}{Замечание}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 20, стр. XXX--YYY (2023) \hspace{65mm}{\rm\small УДК \udcs}}
     \newline
     	{\rm\small DOI~10.17377/semi.2023.10.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}

\thispagestyle{empty}

\title[Приближенные алгоритмы для 2-PSP-2W и 2-CC-2W]{Приближенные алгоритмы для задач
о двух коммивояжерах и о двух цикловых покрытиях на максимум с двумя весовыми функциями}
\author{{А. Н. ГЛЕБОВ, С. С. ЛЫЛОВА, С. Г. ТОКТОХОЕВА}}%
\address{Glebov Aleksey Nikolaevich % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{angle@math.nsc.ru}%

\address{Lylova Sophya Sergeevna % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Novosibirsk State University,
\newline\hphantom{iii} Pirogova Street, 2,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{sophyal@mail.ru}%

\address{Toktokhoeva Surena Garmazhapovna  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Novosibirsk State University,
\newline\hphantom{iii} Pirogova Street, 2,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{s.toktokhoeva@yandex.ru}%

\thanks{\sc Glebov A.N., Lylova S.S., Toktokhoeva S. G.,
Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max}
\thanks{\copyright \ 2022 Глебов A.~Н., Лылова С.~С., Токтохоева С.~Г.}
\thanks{\rm Работа выполнена в рамках государственного задания ИМ СО РАН
(проект №  FWNF-2022-0017).}
\thanks{\it Поступила X декабря 2022 г., опубликована Y октября 2023 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. } We present new polynomial
approximation algorithms for the 2-Perpatetic Salesman
Problem and the 2-Cycle Cover Problem. The $m$-Perpatetic
Salesman Problem ($m$-PSP) is a generalization of the
classical Traveling Salesman Problem. In the $m$-PSP, we
need to find $m$ edge disjoint Hamiltonian cycles of the
extremal total weight in a complete weighted graph
$G=(V,E)$. In the $m$-Cycle Cover Problem ($m$-CC),
we need to find $m$ edge disjoint cycle covers of
the extremal weight in $G$. Many exact and approximation
algorithms were proposed for the case of $m$-PSP
where we are given only one weight function $w:E
\rightarrow {\bf R^+}$ and the weight of $m$ Hamiltonian
cycles $H_1,H_2,\ldots,H_m$ is defined as $w(H_1)+
\ldots +w(H_m)$. However, not so many results are known
for the case when we are given $m$ distinct weight
functions $w_1,w_2,\ldots,w_m$ and the weight of
$H_1,H_2,\ldots,H_m$ is defined as
$w_1(H_1)+w_2(H_2)+\ldots +w_m(H_m)$ (the $m$-PSP-$m$W
problem). Here we present a series of polynomial
algorithms with approximation ratios $1/2$ and higher
for the 2-PSP-max-2W. As a supporting result, we produce
a polynomial algorithm with the asymptotic ratio $\frac 23$
for the 2-CC-max-2W problem.
\medskip

\noindent{\bf Keywords:} Traveling Salesman Problem, 2-Perpatetic
Salesman Problem, Cycle Cover Problem, approximation algorithm,
guaranteed approximation ratio, weight function

 \end{quote}

\section{Введение} %\cite{V76}

Задача об $m$ коммивояжерах ($m$-Perpatetic Salesman Problem
или $m$-PSP) является естественным обобщением классической
задачи коммивояжера (Traveling Salesman Problem или TSP) и
состоит в поиске $m$ реберно непересекающихся гамильтоновых
циклов с минимальным млм максимальным суммарным весом ребер
в полном взвешенном графе $G=(V,E)$. Из результатов работ
\cite{De_Kort,De_Kort1,De_Kort2} следует, что все
содержательные постановки задачи $m$-PSP, как на минимум,
так и на максимум, являются NP-трудными. Поэтому важное
значение имеет разработка полиномиальных приближенных
алгоритмов для разных версий этой задачи. За последние 20
лет было предложено множество таких алгоритмов, однако
большинство из них относятся к случаю, когда во входном
графе $G=(V,E)$ задана всего одна весовая функция ребер
$w:E \rightarrow {\bf R^+}$, которая является общей
для всех гамильтоновых циклов $H_1,H_2,\ldots,H_m$,
составляющих решение задачи. Это означает, что суммарный
вес этих циклов определяется как $w(H_1)+w(H_2)+\ldots
+w(H_m)$.

При указанном предположении, для симметричного варианта
задачи $m$-PSP (когда входной граф является неориентированным,
а веса ребер удовлетворяют тождеству $w(xy)=w(yx)$) были
получены следующие результаты. Агеев и Пяткин \cite{AP_09}
разработали полиномиальный 2-приближённый алгоритм для метрической
версии задачи 2-PSP-min (когда веса ребер удовлетворяют
неравенству треугольника). Для задачи 2-PSP-max с произвольной
весовой функцией в \cite{ABG_3_4,GZ_7_9} были построены
полиномиальные алгоритмы с гарантированными оценкамии $3/4$
и $7/9$. В \cite{GGG} было получено несколько полиномиальных
приближенных алгоритмов, включая алгоритм с оценкой точности
$6/5$, для специального случая задачи 2-PSP-min, когда веса
ребер принимают значения 1 и 2 (задача 2-PSP(1,2)-min).
Для метрического варианта задачи $m$-PSP-max (при произвольном
$m$) в \cite{GG_16} был разработан полиномиальный алгоритм
с гарантированной оценкой $5/6$, а для евклидовой задачи
$m$-PSP-max в \cite{BG_10} был получен асимптотически точный
полиномиальный алгоритм. Для несимметричного варианта задачи
$m$-PSP-max (когда входной граф является ориентированным)
в \cite{GT} был построен полиномиальный алгоритм с
асимптотической оценкой точности 2/3.
%Подробный обзор полученных в указанном направлении результатов
%приводится в \cite{}.

Гораздо меньше результатов было получено для задачи $m$-PSP
в случае, когда во входном графе $G=(V,E)$ задано $m$ весовых
функций $w_1,w_2,\ldots,w_m:E \rightarrow {\bf R^+}$, а
суммарный вес гамильтоновых циклов $H_1,H_2,\ldots,H_m$
определяется как $w_1(H_1)+w_2(H_2)+\ldots +w_m(H_m)$ (так
называемая задача $m$-PSP-$m$W). Так в работах \cite{GZ_7_5,
GZ_4_3} исследовалась постановка задачи 2-PSP-min-2W с весами
ребер 1 и 2 и были предложены полиномиальные алгоритмы с оценками
точности $7/5$ \cite{GZ_7_5} и $4/3$ \cite{GZ_4_3}. В \cite{Gord}
для метрической задачи 2-PSP-max-2W был получен полиномиальный
алгоритм с асимптотической оценкой 11/16. При этом ни в одной
из ранее опубликованных работ ни при каком $m\ge 2$ не был
предложен полиномиальный алгоритм с гарантированной оценкой
точности в наиболее общем случае задачи $m$-PSP-$m$W, когда
весовые функции $w_1,w_2,\ldots,w_m$ принимают произвольные
неотрицательные значения.

В настоящей статье впервые получена серия полиномиалных
приближенных алгоритмов с оценками точности 1/2 и выше для
задачи 2-PSP-max-2W а также для связанной с ней задачи о двух
реберно непересекающихся цикловых покрытиях максимального
суммарного веса в графе с двумя весовыми функциями (задача
2-CC-max-2W).

В разделе 2 статьи вводятся необходимые
определения и обозначения. В разделах 3 и 4 описываются
полиномальные 1/2-приближенные алгоритмы для задачи
2-PSP-max-2W в ее симметричной и несимметричной постановках
соответственно. Раздел 5 посвящен обоснованию того, что
оценка точности 1/2 полученных выше алгоритмов является
неулучшаемой в определенном смысле. В разделе 6 разработан
полиомиальный приближенный алгоритм для задачи 2-CC-max-2W
с асимптотической оценкой точности $\frac 23$.
В заключительном разделе 7, основываясь на методах
и подходах из раздела 6, построен полиномиальный алгоритм
для задачи 2-PSP-max-2W, оценка точности которого
превышает 1/2.

Отметим, что задача об $m$ реберно непересекающихся цикловых
покрытиях максимального веса в графе с одной весовой функцией
(задача $m$-CC-max) является полиономиально разрешимой при
любом значении $m$. Однако сложностной статус задачи
$m$-CC-max-$m$W при $m\ge 2$ нам не известен.

\section{Основные определения и обозначения}

Пусть $G=G(V,E,w_1,w_2)$ --- полный неориентированный или
ориентированный граф с $n$ вершинами и неотрицательными
весовыми функциями ребер (дуг) $w_1 : E \rightarrow
\mathbb{R}^+$ и $w_2 : E \rightarrow \mathbb{R}^+$.
Для каждого подграфа $G'$ графа (орграфа) $G$ через $w(G')$
обозначается суммарный вес ребер (дуг), составляющих $G'$.

Для каждой вершины $v\in V$ (ор)графа $G$ через $d(v)$
обозначим \textit{степень вершины} $v$, то есть количество
инцидентных $v$ ребер (дуг). В случае ориенитрованного графа
$G$ будем также использовать следующие обозначения:

$d^{+}(v)$ --- \textit{полустепень исхода} --- количество
исходящих из $v$ дуг;

$d^{-}(v)$ --- \textit{полустепень захода} --- количество
входящих в $v$ дуг;

Ясно, что $d(v)=d^{+}(v)+d^{-}(v)$ для любой вершины $v\in V$.

Подграф $G'$ неориентированного графа $G$ называется
$k$-\textit{регулярным}, если для каждой его вершины $v$
выполняется равенство $d(v)=k$. Подграф $G'$ ориентированного
графа $G$ будем называть $(k,k)$-\textit{регулярным},
если для каждой его вершины $v$ выполняются равенства
$d^{+}(v)=d^{-}(v)=k$. \textit{Цикловым покрытием} или
2-\textit{фактором} (\textit{ориентированным $2$-фактором})
в неориентированном (ориентированном) графе $G$ называется
любой его остовный 2-регулярный ((1,1)-регулярный) подграф,
то есть набор из вершинно непе\-ре\-се\-каю\-щих\-ся циклов
(контуров), покрывающих все вершины $G$.

\textit{Частичным туром} $T$ в графе (орграфе) $G$
назовем набор вершинно непересекающихся (ориентированных)
цепей, покрывающих все вершины $G$. \textit{Смешанным туром}
в (ор)графе) $G$ назовем набор вершинно непересекающихся
(ориентированных) цепей и циклов, покрывающих все вершины $G$.
При этом некоторые цепи могут состоять из одной вершины; будем
называть такие цепи (\textit{синглами}), а цепи, состоящие из
более чем одной вершины --- {\it нетривиальными} цепями.
Через $|T|$ и $p(T)$ обозначается число ребер и число цепей
в смешанном туре $T$, соответственно. Ясно, что для любого
смешанного тура $T$ выполнянтся равенство:%\setcounter{equation}
%\begin{equation}\label{eq1}
$|T|+p(T)=|V(G)|$.
%\end{equation}

Заметим, что любой частичный тур $T$ в графе (орграфе) $G$
можно дополнить до (ориентированного) гамильтонова цикла $H$,
добавляя к $T$ ребра (дуги), соединяющие концевые вершины
цепей тура $T$. При этом, в силу неотрицательности весовых
функций $w_1$ и $w_2$, справедлмвы неравенства $w_1(H)\ge
w_1(T)$ и $w_2(H)\ge w_2(T)$. Также очевидно, что из любого
циклового покрытия или смешанного тура $Z$ (ор)графа $G$
можно получить частичный тур $T$, удаляя из $Z$ часть ребер
(хотя бы по одному ребру из каждого цикла в $Z$). При этом
выполняются неравенства $w_1(T)\le w_1(Z)$ и $w_2(T)\le w_2(Z)$.

\textit{Двудольной моделью орграфа} $G$ назовем двудольный
неориентированный граф $B$ c долями $V=V(G)$ и $V^{\prime}$,
где $V^{\prime}$ --- множество дубликатов всех вершин
орграфа $G$, и $\{ X,Y^{\prime}\} \in E(B)\Leftrightarrow
(X,Y)\in E(G)$.

Симметричная (несимметричная) задача о двух коммивояжёрах
на максимум с двумя различныим весовыми функциями обозначается
через 2-PSP-max-2W (2-APSP-max-2W) и заключается в нахождении
двух непересекающихся по ребрам (дугам) (ориентированных)
гамильтоновых циклов $H_{1},\:H_{2}$ в графе (орграфе) $G$,
для которых суммарный вес составляющих их ребер (дуг) максимален:
$$w_1(H_1)+w_2(H_2) \rightarrow \max$$
(в ориентированном случае допускается, что цикл $H_{i}$ содержит
дугу $(X,Y)$, а цикл $H_{j}$ содержит встречную дугу $(Y,X)$).
Через $w^{*}$ будем обозначать вес оптимального решения задачи
2-PSP-max-2W (2-APSP-max-2W).

\medskip
Далее в статье приводится описание и анализ приближенных
алгоритмов $A_{1/2}$ и $\widetilde{A}_{1/2}$ для задач
2-PSP-max-2W и 2-APSP-max-2W. Основная идея обоих алгоритмов
заключается в нахождении в графе двух цикловых покрытий
максимального веса относительно весовых функций $w_1$ и $w_2$
соответственно и последующем преобразовании этих покрытий в два
реберно непересекающихся гамильтоновых цикла, составляющих
искомое $\frac 12$-приближенное решение задачи.

%Для реализации этой идеи на стадии
%замыкания туров в гамильтоновы циклы требуется, чтобы число вершин
%орграфа было не меньше 15. При меньшем числе вершин предлагается
%использовать алгоритм полного перебора для отыскания оптимального
%решения задачи 2-PSP-2w-max (2-APSP-2w-max).


\section{Алгоритм $A_{1/2}$ для задачи 2-PSP-max-2W}

Если $n\le 14$, то с помощью полного перебора находим в графе $G$
два непересекающихся по ребрам гамильтоновых цикла $H_1^*,H_2^*$,
составляюших оптимальное решением задачи 2-PSP-max-2W. Предположим,
что $n \ge 15$.

\smallskip
\textit{Этап 1.} С помощью алгоритма Габова из \cite{Gabow}
находим в графе $G$ цикловое покрытие $C_1$, имеющее наибольший
вес $w_1(C_1)$. Далее c помощью того же алгоритма находим в $G$
цикловое покрытие $C_2$, имеющее наибольший вес $w_2(C_2)$.
Поскольку каждый из гамильтоновых циклов $H_1^*$ и $H_2^*$
является цикловым покрытием $G$, то выполняются неравенства
$w_1(C_1) \geq w_1(H_1^*)$ и $w_2(C_2) \geq w_2(H_2^*)$.
Следовательно, $w_1(C_1) + w_2(C_2)\geq w^*$. При этом
цикловые покрытия $C_1$ и $C_2$ могут иметь общие ребра.

\smallskip
\textit{Этап 2.} Удалим из цикловых покрытий $C_1$ и $C_2$ часть
ребер, применяя алгоритм удаления ребер, описанный в разделе 3.1.
В результате получим два реберно-непересекающихся частичных тура
$T_{1},T_{2}$, для веса которых справедливо неравенство
$$w_1(T_{1})+w_2(T_{2}))\geq \frac{1}{2}w_1(C_{1})+w_2(C_{2}))
\geq \frac{1}{2}w^*.$$
При этом каждый из туров $T_{1},T_{2}$ состоит не менее чем из
трех цепей, и длина любой его цепи не превосходит 5.

\smallskip
\textit{Этап 3.} Используя процедуру $T\rightarrow H$, описанную
в разделе 3.2 и основанную на процедуре $T^{3n}\rightarrow H$
из работы \cite{GGG}, дополняем тур $T_{1}$ до гамильтонова
цикла $H_{1}$, не имеющего общих ребер с туром $T_{2}$. Далее
с помощью той же процедуры $T\rightarrow H$ дополняем тур
$T_{2}$ до гамильтонова цикла $H_{2}$, не используя ребер
из уже построенного цикла $H_{1}$. Предъявляем пару реберно
непересекающихся гамильтоновых циклов $H_{1}$ и $H_{2}$
в качестве искомого 1/2-приближенного решения задачи
2-PSP-max-2W.

\medskip
Основные свойства данного алгоритма описываются следующей теоремой.

\medskip
{\bf Теорема 1.} {\em Представлннный выше алгоритм $A_{1/2}$
находит в полном взвшенном неориентированном графе $G=(V,E,
w_1,w_2)$ два реберно непересекающихся гамильтоновых цикла
$H_{1},\:H_{2}$, суммарный вес которых удовлетворяет неравенству
$w_1(H_{1})+w_2(H_{2})\ge \frac{1}{2}w^*$. Время работы
алгоритма $A_{1/2}$ оценивается как $O(n^3)$, где $n$ --- число
вершин графа $G$.}

\medskip
Доказательство этой теоремы приводится в разделе 3.3.

\subsection{Процедура построения частичных туров} ~\\
Процедура получает на вход два цикловых покрытия $C_1$ и $C_2$
с максимальным суммарным весом относительно функций $w_1$
и $w_2$ соответственно. Далее происходит удаление части ребер
из $C_1$ и $C_2$ с целью получения реберно непересекающихся
частичных туров $T_1$ и $T_2$ необходимого веса.

Назовём ребро графа $G$ \textit{двойным}, если оно входит в оба
цикловых покрытия $C_1$ и $C_2$, и \textit{одиночным}, если оно
принадлежит только одному из этих покрытий.

\smallskip
\textbf{Процедура удаления  двойных ребер.}{\par}
Рассмотрим в графе $G$ подграф $D$ с множеством вершин $V$
и множеством всех двойных ребер $G$. Ясно, что $D$ является
подграфом каждого из цикловых покрытий $C_1$ и $C_2$.
Следовательно, $D$ --- это смешанный тур в $G$.

Рассмотрим произвольную компоненту связности $P$ (цепь или цикл)
в $D$. Пусть $P = v_0,e_1,v_1,e_2,v_2,\ldots,e_k,v_k$, где
$v_k=v_0$, если $P$ является циклом. Определим две суммы весов ребер:
$$W_1 = w_2(e_1) + w_1(e_2) + w_2(e_3) + w_1(e_4) + \ldots $$
$$W_2 = w_1(e_1) + w_2(e_2) + w_1(e_3) + w_2(e_4) + \ldots $$
Если $W_1 > W_2$, то удалим из $C_1$ ребра $e_1, e_3, e_5, \ldots$,
а из $C_2$ удалим ребра $e_2, e_4, e_6, \ldots$. Если $W_2 \geq W_1$,
то удалим из $C_1$ ребра $e_2, e_4, e_6, \ldots$, а из $C_2$ удалим
ребра $e_1, e_3, e_5, \ldots$. В результате в каждом из цикловых
покрытий $C_1$, $C_2$ будет удалено каждое второе ребро цепи
(цикла) $P$, а суммарный вес всех удаленных ребер не превосходит
$\frac{1}{2}(W_1+ W_2) = \frac{1}{2}(w_1(P) + w_2(P))$. При этом
для каждого $i=1,2$, все не удаленные из $C_i$ ребра цепи (цикла)
$P$ попарно несмежны, за исключением, возможно, пары ребер $e_1,e_k$,
в случае, когда $P$ является циклом нечетной длины $k$.

\smallskip
\textbf{Процедура удаления одиночных ребер.}{\par}
Рассмотрим произвольный цикл $C$ в $C_1$. Обозначим через
$U = e_1, e_2,e_3, \ldots, e_t$ последовательность всех одиночных
ребер из $C$, где ребра обозначены в порядке их обхода по циклу.
Определим две суммы весов ребер:
$$W_1 = w_1(e_1) + w_1(e_3) + w_1(e_5) + \ldots $$
$$W_2 = w_1(e_2) + w_1(e_4) + w_1(e_6) + \ldots $$
Если $W_1 > W_2$, то удалим из $C_1$ ребра $e_2, e_4, e_6, \ldots$.
Если $W_2 \geq W_1$, то удалим из $C_1$ ребра $e_1, e_3, e_5,\ldots$.
Заметим, что сумма весов всех удаленных одиночных ребер цикла $C$
не превосходит $\frac 12 w_1(U)$. Аналогично поступим с каждым циклом
из $C_1$ и из $C_2$, при этом ребра из $C_2$ будем рассматривать
относительно весеовой функции $w_2$.

\medskip
{\bf Лемма 1.} {\it В результате применения процедур удаления
двойных и одиночных ребер цикловые покрытия $C_1$ и $C_2$
преобразуются в реберно непересекающиеся частичные туры $T_{1}$
и $T_{2}$. Длина любой цепи в каждом из туров $T_{1},T_{2}$
не превосходит $5$. При этом выполняется неравенство }
$$w_1(T_{1})+w_2(T_{2})\geq \frac{1}{2} (w_1(C_{1})+w_2(C_{2}))\geq
\frac{1}{2}w^*.$$

\smallskip
{\it Доказательство.} Из описания процедур сразу следует, что $T_1$
и $T_2$ --- это смешанные туры в $G$, не содержащие общих ребер,
для которых выполняется требуемое неравенство. Докажем, что $T_1$
и $T_2$ являются частичными турами. Для этого достаточно убедиться,
что из каждого цикла $C$ в каждом из цикловых покрытий $C_1,C_2$
удаляется хотя бы одно ребро. Действительно, если цикл $C$ содержит
хотя бы два одиночных ребра, то одно из них удаляется процедурой
удаления одиночных ребер. В противном случае $C$ содержит цепь
из $|C|-1 \ge 2$ двойных ребер, и хотя бы одно из них удаляется
процедурой удаления двойных ребер.

Остается доказать, что длина любой цепи в каждом из туров $T_{1},
T_{2}$ не превосходит 5. Пусть $P$ --- произвольная цепь из $T_1$
(для цепи из $T_2$ доказательство аналогично). Рассмотрим
в цикловом покрытии $C_1$ цикл $C = (v_0,v_1,\ldots,v_{k-1},v_0)$,
содержащий цепь $P$. Если все ребра $C$ изначально были двойными,
то после процедуры удаления двойных рёбер цепь $P$ может содержать
только одно или два ребра (а именно, ребра $e_1=v_0v_1$ и $e_k=
v_{k-1}v_0$, в случае нечетного $k$). Пусть цикл $C$ содержит
хотя бы одно одиночное ребро. Без потери общности, можно считать,
что ребро $e_1=v_0v_1$ является одиночным. Из процедур удаления
ребер следует, что в цепи $P$ не может быть двух последовательных
двойных рёбер и есть только одно или два одиночных ребра, а именно,
ребра $e_1=v_0v_1$ и $e_t=v_{j-1}v_j$ при нечетном $t$.
Если цепь $P$ содержит только одно одиночное ребро $v_{i-1}v_i$,
то она может содержать еще только два двойных ребра: $v_{i-2}
v_{i-1}$ и $v_iv_{i+1}$. В этом случае длина $P$ не превосходит
3. Если же цепь $P$ содержит одиночные ребра $e_1=v_0v_1$ и
$e_t=v_{j-1}v_j$, то она может содержать еще только три двойных
ребра: $v_{j-2}v_{j-1}$, $v_jv_0$ и $v_1v_2$ (при $j=k-1$).
В этом случае длина цепи $P$ не превосходит 5. \, Лемма 1 доказана.

\subsection{Процедура $T\rightarrow H$ замыкания частичного тура
в гамильтонов~цикл} ~\\
В статье \cite{GGG} была описана процедура, которая, получая
на вход частичный тур $T$ и частичный тур или гамильтонов цикл
$S$, не имеющий общих ребер с $T$, за время $O(n)$ дополняет
тур $T$ до гамильтонова цикла $H$, не имеющего общих ребер
с $S$. Условием корректной работы этой процедуры является
наличие в туре $T$ не менее трех нетривиальных цепей. Поэтому
сначала мы добьемся того, чтобы каждый из построенных на Этапе 2
алгоритма частичных туров $T_{1},T_{2}$ содержал не менее трех
нетривиальных цепей.

Согласно лемме 1 каждая цепь в $T_{1}$ и $T_{2}$ содержит
не более шести вершин. Из неравенства $n \geq 15$ следует, что
число цепей в каждом из туров $T_{1}$ и $T_{2}$ не меньше трех.
Если хотя бы три из этих цепей являются нетривиальными, то
получаем требуемое. Если тур $T_{1}$ содержит только две
нетривиальные цепи, то общее число вершин в этих цепях не
больше 12, а значит, $T_{1}$ содержит по крайней мере $15-12=3$
сингла. Поскольку в туре $T_{2}$ нет треугольников, то какие-то
два из этих синглов не соединены ребром в $T_{2}$. Добавляя ребро
между ними к туру $T_{1}$, получаем третью нетривиальную цепь
в $T_{1}$. Если тур $T_{1}$ содержит только одну нетривиальную
цепь, то в нем есть не менее $15–6 = 9$ синглов, из которых можно
составить две тройки синглов, и в каждой тройке соединить какие-то
два сингла ребром. В результате получаем три нетривиальных цепи
в туре $T_{1}$. Аналогично поступаем с туром $T_{2}$.

Теперь, когда каждый из туров $T_{1}$, $T_{2}$ содержит хотя бы
по три нетривиальных цепи, при помощи упомянутой выше процедуры
из \cite{GGG}, дополняем частичный тур $T_{1}$ до гамильтонова
цикла $H_{1}$, не имеющего общих ребер с туром $T_{2}$. Далее
при помощи той же процедуры дополняем тур $T_{2}$ до
гамильтонова цикла $H_{2}$, не имеющего общих ребер с уже
построенным циклом $H_{1}$. В итоге получаем два реберно
непересевающихся гамильтоновых цикла $H_{1}$ и $H_{2}$,
составляющих искомое приближенное решение задачи 2-PSP-max-2W.

\subsection{Доказательство теоремы 1} ~\\
Из неравенства в лемме 1, неотрицательности весовых функций $w_{1},
w_{2}$ и того факта, что построеннные процедурой $T\rightarrow H$
гамильтоновы циклы $H_{1}$ и $H_{2}$ содержат все ребра частичных
туров $T_{1}$ и $T_{2}$ соответственно, следует, что $$w_1(H_{1})+
w_2(H_{2}) \geq w_1(T_{1})+w_2(T_{2}) \geq \frac{1}{2}w^*.$$
Трудоемкость алгоритма $A_{1/2}$ опредеяется временем работы
алгоритма Габова на Этапе 1, которое оценивается как $O(n^3)$.
\, Теорема 1 доказана.

\section{Алгоритм $\widetilde{A}_{1/2}$ для задачи 2-APSP-max-2W}

Приведенный ниже алгоритм$\widetilde{A}_{1/2}$  основан на
тех же идеях, что и алгоритм $A_{1/2}$ для задачи 2-PSP-max-2W,
но имеет ряд отличий.

Если $n\le 18$, то с помощью полного перебора находим в орграфе $G$
два непересекающихся по ребрам ориентированных гамильтоновых цикла
$H_{1},H_{2}$, являющиеся оптимальным решением задачи 2-APSP-max-2W.
Предположим, что $n>18$. %должно быть не 10, надо будет рассчитать

\smallskip
\textit{Этап 1.} Находим в $G$ два ориентированных цикловых покрытия
$C_1$ и $C_2$ с максимальным суммарным весом дуг относительно
функций $w_1$ и $w_2$ соответственно. Для поиска $C_1$ и $C_2$
используем двудольную модель $B$ орграфа $G$, в которой за время
$O(n^{3})$ находим два совершенных паросочетания максимального веса
относительно каждой из весовых функций. Найденным паросочетаниям
в $B$ соответствуют искомые цикловые покрытия $C_1$ и $C_2$
максимального веса в $G$.

\smallskip
\textit{Этап 2.} Используя процедуру ``Построение ориентированных
частичных туров'', описанную в разделе 4.1, выделим в $C_1 \bigcup
C_2$ два реберно непересекающихся частичных тура $T_{1},T_{2}$,
суммарный вес которых удовлетворяет неравенству:
$$w_1(T_{1})+w_2(T_{2})\geq\frac{1}{2}(w_1(C_{1})+w_2(C_{2}))\geq
\frac{1}{2}w^*.$$

\smallskip
\textit{Этап 3.} При помощи процедуры ``Замыкание ориентированных
частичных туров в гамильтоновы циклы'', описанной в разделе 4.2,
дополним полученные на Этапе 2 частичные туры $T_{1},T_{2}$ до
реберно непресекающихся ориентированных гамильтоновых циклов
$H_{1},H_{2}$, суммарный вес которых удовлетворяет неравенству:
$$w_1(H_{1})+w_2(H_{2})\geq w_1(T_{1})+w_2(T_{2})\geq
\frac{1}{2}w^*.$$
Предъявляем пару гамильтоновых циклов $H_{1},H_{2}$ в качестве
искомого приближенного решения задачи 2-APSP-max-2W.

\medskip
Основным результатом данного раздела статьи являются следующая

\medskip
{\bf Теорема 2.} {\em Представлнный выше алгоритм
$\widetilde{A}_{1/2}$  находит в полном взвшенном
ориентированном графе $G=(V,E,w_1,w_2)$ два реберно
непересекающихся ориентированных гамильтоновых цикла
$H_{1},\:H_{2}$, суммарный вес которых удовлетворяет
неравенству $w_1(H_{1})+w_2(H_{2})\ge \frac{1}{2}w^*$.
Время работы алгоритма $A_{1/2}$ оценивается как $O(n^3)$,
где $n$ --- число вершин орграфа $G$.}

\medskip
Доказательство теоремы 2 приводится в разделе 4.3. В разделе 5
доказыается, что в рамках используемого нами подхода оценка
точности $1/2$ алгоритмов $A_{1/2}$ и $\widetilde{A}_{1/2}$
является неулучшаемой.

\subsection{Построение ориентированных частичных туров} ~\\
Процедура получает на вход два ориентированных цикловых покрытия
$C_1$ и $C_2$ с максимальным суммарным весом относительно функций
$w_1$ и $w_2$ соответственно. Далее процедура строит частичные
туры необходимого веса путем удаления дуг из цикловых покрытий
$C_1$ и $C_2$.

Назовём дугу $e = (x,y)$ \textit{двойной}, если она входит
в оба цикловых покрытия $C_1$ и $C_2$, и \textit{одиночной},
если она входит только в одно из покрытий. Назовем двойную
дугу $e = (x,y)$ \textit{сингулярной относительно $C_i$},
если встречная дуга $e'=(y,x)$ принадлежит цикловому покрытию
$C_i$, то есть если $C_i$ содержит цикл $(x,e,y,e',x)$ длины 2.
Назовем сингулярную дугу $e = (x,y)$ \textit{2-сингулярной},
если встречная дуга $e'=(y,x)$ принадлежит обоим цикловым
покрытиям $C_1$ и $C_2$, и \textit{1-сингулярной}, если $e'$
принадлежит только одному из покрытий $C_1$ или $C_2$.
Назовем дугу $e=(x,y)$ циклового покрытмя $C_i$ {\it
квазиодиночной}, если она либо одиночная, либо 1-сингулярная
относительно $C_{3-i}$. В последнем случае дуги $e'=(y,x)$
и $e''=(x,y)$ покрытия $C_{3-i}$ будем называть
{\it дополняющими} (для $e$).

\smallskip
\textbf{Процедура удаления двойных дуг.}{\par}
Определим орграф $D$ как остовный подграф в $G$, состоящий
из всех 2-сингулярных двойных дуг и всех двойных дуг,
не являющихся сингулярными. Ясно, что каждая компонента
связности $D$ является цепью или циклом. Пусть $P = v_0,e_1,
v_1,e_2,v_2,\ldots,e_k,$ $v_k$ –-- произвольная компонента
связности в $D$, где $v_k=v_0$, если $P$ является циклом.

Если $P$ содержит 2-сингулярную дугу $e_i=(v_{i-1},v_i)$,
то каждое из цикловых покрытий $C_1$ и $C_2$ содержит обе дуги
$e_i=(v_{i-1},v_i)$ и $e'_i=(v_i,v_{i-1})$, а значит, содержит
цикл $Z=(v_{i-1},e_i,v_i,e'_i,v_{i-1})$ длины 2. Отсжда следует,
что $k=2$, $i=1$ и $P=Z=(v_0,e_1,v_1,e'_1,v_0)$. Если $w_1(e_1)
+w_2(e'_1) < w_2(e_1)+w_1(e'_1)$, то удалим из $C_1$ дугу $e_1$,
а из $C_2$ удалим дугу $e'_1$. В противном случае удалим из
$C_1$ дугу $e'_1$, а из $C_2$ удалим дугу $e_1$.

Пусть $P$ не содержит 2-сингулярных (а значит, и вообще
сингулярных) дуг. Определим две суммы весов дуг:
$$W_1 = w_2(e_1) + w_1(e_2) + w_2(e_3) + w_1(e_4) + \ldots $$
$$W_2 = w_1(e_1) + w_2(e_2) + w_1(e_3) + w_2(e_4) + \ldots $$
Если $W_1 > W_2$, то удалим из $C_1$ дуги $e_1, e_3, e_5, \ldots$,
а из $C_2$ удалим дуги $e_2, e_4, e_6, \ldots$. Если $W_2 \geq
W_1$, то удалим из $C_1$ дуги $e_2, e_4, e_6, \ldots$, а из
$C_2$ удалим дуги $e_1, e_3, e_5, \ldots$. В результате в каждом
из цикловых покрытий $C_1$, $C_2$ будет удалена каждая вторая
дуга цепи (цикла) $P$, а суммарный вес всех удалённых дуг не
превосходит $\frac{1}{2}(W_1+ W_2) = \frac{1}{2}(w_1(P) + w_2(P))$.

\smallskip
\textbf{Процедура удаление квазиодиночных и дополняющих дуг.}{\par}
Рассмотрим по отдельности каждый цикл $C$ покрытия $C_1$.
Если $C$ состоит только из двойных дуг, то $C$ принадлежит
также цикловому покрытию $C_2$, а значит, является компонентой
связности в орграфе $D$. В этом случае удаление дуг из $C$
выполняется согласно процедуре удаления двойных дуг.
%В результате удаления дуг из $C_1$ и $C_2$, получаем частичные
%туры $T_1(C)$ и $T_2(C)$ в компоненте связности $C$. При этом
%выполняется неравенство $\frac{1}{2}(w_1(T_1(C)) + w_2(T_2(C)))
%\geq \frac{1}{2}(w_1(C) + w_2(C))$.

%Если $C$ состоит только из одиночных дуг, то, как и
%в неориентированном случае, определим две суммы весов дуг:
%$$W_1 = w_1(e_1) + w_1(e_3) + w_1(e_5) + \ldots $$
%$$W_2 = w_1(e_2) + w_1(e_4) + w_1(e_6) + \ldots $$
%Если $W_1 > W_2$, то удалим из $C_1$ дуги $e_2, e_4, e_6, \ldots$.
%Если $W_2 \geq W_1$, то удалим из $C_1$ дуги $e_1, e_3, e_5, \ldots$.
%%В результате удаления дуг из $C_1$, получаем частичный тур $T_1(C)$
%%в компоненте связности $C$.
%Заметим, что сумма весов всех удаленных дуг цикла $C$ не превосходит
%$\frac{1}{2}w_1(C)$.
%%Поэтому справедливо неравевенство $\frac{1}{2}w_1(T_1(C)) \geq
%\frac{1}{2}w_1(C)$.

Пусть цикл $C$ содержит хотя бы одну одиночную дугу. Обозначим
через $U = e_1, e_2, e_3, \ldots, e_t$ последовательность всех
квазиодиночных дуг из $C$, где дуги обозначены в порядке их
обхода по циклу. Для каждой 1-сингулярной дуги $e_i=(u,v)$
обозначим через $e'_i=(v,u)$ и $e''_i=(u,v)$ дополняющие ее
дуги циклового покрытия $C_2$. Для каждой одиночной дуги $e_j$
из $U$ также формально введем обозначения $e'_j$ и $e''_j$,
считая $e'_j$ и $e''_j$ фиктивными дугами и полагая $w_2(e'_j)=
w_2(e''_j)=0$. Определим две суммы весов дуг:
$$W_1 = (w_1(e_1) + w_2(e'_1)) + w_2(e''_2) + (w_1(e_3) + w_2(e'_3))
+ w_2(e''_4) + \ldots $$
$$W_2 = w_2(e''_1) + (w_1(e_2) + w_2(e'_2)) + w_2(e''_3) + (w_1(e_4)
+ w_2(e'_4)) + \ldots $$
Если $W_1 > W_2$, то удалим из $C_1$ дуги $e_2, e_4, e_6, \ldots$,
а из $C_2$ удалим дуги $e''_1, e'_2, e''_3, e'_4, \ldots$. Если
$W_2 \ge W_1$, то удалим из $C_1$ дуги $e_1, e_3, e_5, \ldots$,
а из $C_2$ удалим дуги $e'_1, e''_2, e'_3, e''_4, \ldots$
(разумеется, речь идет об удалении из $C_2$ только реально
существующих дуг, дополняющих 1-сингулярные дуги цикла $C$).

Заметим, что сумма весов всех удаленных дуг не превосходит
$\frac 12 \sum_{i=1}^t (w_1(e_i)+w_2(e'_i)+w_2(e''_i))$,
то есть не превосходит полусуммы весов всех квазиодиночных
и дополняющих дуг для цикла $C$. Применим описанную процедуру
к каждому циклу из $C_1$ и $C_2$.

\medskip
{\bf Лемма 2.} {\it В результате процедур удаления двойных,
квазиодиночных и дополняющих дуг цикловые покрытия $C_1$ и $C_2$
преобразуются в реберно непересекающиеся частичные туры $T_{1}$
и $T_{2}$. Длина любой цепи в каждом из туров $T_{1},T_{2}$ не
превосходит $5$. При этом выполняется неравенство }
$$w_1(T_{1})+w_2(T_{2})\geq \frac{1}{2} (w_1(C_{1})+w_2(C_{2}))\geq
\frac{1}{2}w^*.$$

\smallskip
{\it Доказательство.} Из описания процедур следует, что $T_1$
и $T_2$ --- это смешанные туры без общих дуг, для веса которых
выполняется требуемое неравенство. Докажем, что $T_1$ и $T_2$
являются частичными турами, то есть из каждого цикла $C$ в каждом
из цикловых покрытий $C_1,C_2$ удаляется хотя бы одна дуга.
Если цикл $C$ имеет длину не меньше 3 и содержит хотя бы две
квазиодиночные дуги, то одна из них удаляется процедурой удаления
квазиодиночных и дополняющих дуг. Если $C$ имеет длину не меньше
3 и содержит не более одной квазиодиночной дуги, то $C$ содержит
цепь из $|C|-1 \ge 2$ двойных дуг, хотя бы одна из которых
удаляется процедурой удаления двойных дуг. Пусть $C$ --- цикл
длины 2 в $C_i$. Если обе дуги в $C$ являются одиночными, то одна
из них удаляется процедурой удаления квазиодиночныхи и дополняющих
дуг. Если ровно одна дуга в $C$ является одиночной, то цикл $C$
состоит из двух дополняющих дуг для некоторой 1-сингулярной
дуги покрытия $C_{3-i}$. В этом случае одна из дуг цикла $C$
также удаляется процедурой удаления квазиодиночныхи и дополняющих
дуг. Наконец, если цикл $C$ образован двумя двойными дугами, то
обе они являются 2-сингулярными, а значит, одна из них удаляется
процедурой удаления двойных дуг.

Остается доказать, что длина любой цепи в каждом из туров $T_{1},
T_{2}$ не превосходит 5. Пусть $P$ --- цепь из $T_1$, и пусть
$C = (v_0,v_1,\ldots,v_{k-1},v_0)$ --- цикл из $C_1$ длины
$k>2$, содержащий $P$. Если цикл $C$ состоит только из двойных дуг,
то после процедуры удаления двойных дуг цепь $P$ будет содержать
только одну или две дуги ($e_1=(v_0,v_1)$ и $e_k=(v_{k-1},v_0)$,
в случае нечетного $k$). Пусть $C$ содержит одиночную дугу
$e_1=(v_0,v_1)$. Из процедур удаления двойных и квазиодиночных
дуг следует, что в цепи $P$ не может быть двух последовательных
двойных дуг и может быть всего одна или две квазиодиночные дуги,
а именно, дуги $e_1=(v_0,v_1)$ и $e_t=(v_{j-1},v_j)$ при нечетном
$t$. Отсюда аналогично доказательству леииы 1 выводится, что длина
цепи $P$ не превосходит 5. \, Лемма 2 доказана.

\subsection{Замыкание ориентированных частичных туров
в гамильтоновы циклы} ~\\
В статье \cite{GZS} была описана процедура, которая, получая
на вход ориентированный частичный тур $T$ и ориентированный
частичный тур или гамильтонов цикл $S$, не имеющий общих дуг
с $T$, за время $O(n)$ дополняет тур $T$ до ориентированного
гамильтонова цикла $H$, не имеющего общих дуг с $S$. Условием
корректной работы этой процедуры является наличие в туре $T$
не менее четырех цепей (среди которых могут быть синглы).

Так как $n>18$, и по лемме 2 каждая цепь туров $T_{1}$ и
$T_{2}$ содержит не более шести вершин, то каждый из этих
туров состоит не менее чем из четырех цепей. Применяя процедуру
из \cite{GZS}, сперва дополняем частичный тур $T_{1}$ до
ориентированного гамильтонова цикла  $H_{1}$, не имеющего
общих дуг с туром $T_{2}$. Далее при помощи той же процедуры
дополняем тур $T_{2}$ до ориентированного гамильтонова цикла
$H_{2}$, не имеющего общих дуг с уже построенным циклом $H_{1}$.
В итоге получаем два ориентированных гамильтоновых цикла $H_{1}$
и $H_{2}$ без общих дуг, составляющих искомое приближенное
решение задачи 2-APSP-max-2W.

\subsection{Доказательство теоремы 2} ~\\
Из неравенства в лемме 2, неотрицательности весовых функций
$w_{1},w_{2}$ и того факта, что построеннные гамильтоновы
циклы $H_{1}$ и $H_{2}$ содержат все дуги частичных туров
$T_{1}$ и $T_{2}$ соответственно, следует, что $$w_1(H_{1})+
w_2(H_{2}) \geq w_1(T_{1})+w_2(T_{2}) \geq \frac{1}{2}w^*.$$
Трудоемкость алгоритма $A_{1/2}$ опредеяется временем отысканя
ориентированных цикловых покрытий $C_1,C_2$ на Этапе 1, которое
оценивается как $O(n^3)$. \, Теорема 2 доказана.


\section{''Неулучшаемость'' оценки точности $1/2$} ~\\
Нетрудно заметить, что если в качестве верхней границы для веса
оптимального решения в задачах 2-PSP-max-2W и 2-APSP-max-2W
использовать величину $w^*_1 + w^*_2$, где $w^*_1$ и $w^*_2$
--- это оптимумы для задачи о максимальном цикловом покрытии
с весовыми функциями $w_1$ и $w_2$ соответственно (как это
делается выше при анализе алгоритмов $A_{1/2}$ и
$\widetilde{A}_{1/2}$), то полученную оценку точности
$1/2$ относительно этой верхней границы улучшить невозможно.

Действительно, рассмотрим входной граф (орграф) $G=(V,E,w_1,
w_2)$, где $w_1=w_2$, и веса всех ребер некоторого
(ориентированного) гамильтонова цикла $H$ равны 1, а веса
всех остальных ребер графа равны нулю.
%(относительно обеих весовых функций).
В этом случае справедливы равенства
$w^*_1 = w^*_2 = n$, причем единственным максимальным
цикловым покрытием относительно любой из весовых функций
является гамильтонов цикл $H$. При этом для веса оптимального
решения задачи 2-PSP-max-2W (2-APSP-max-2W) также выполняется
равенство $w^* = n$, поскольку в графе $G$ только ребра цикла
$H$ имеют ненулевой вес, равный 1, и каждое из этих ребер
может принадлежать только одному из гамильтоновых циклов,
составляющих оптимальное решение задачи 2-PSP-max-2W
(2-APSP-max-2W). Поэтому для веса оптимального решения
выполняется равенство $w^* = \frac 12 (w^*_1 + w^*_2) = n$,
что не позволяет получить для задач 2-PSP-max-2W и 2-APSP-max-2W
приближенных алгоритмов с оценками точности выше $1/2$ по
отношению к сумме $w^*_1 + w^*_2$. Приведенный пример
показывает, что данный вывод остается в силе и в том случае,
если в качестве $w^*_1$ и $w^*_2$ рассматривать оптимумы для
задачи коммивояжера TSP-max с весовыми функциями $w_1$ и $w_2$
соответственно.

Сделанное замечание указывает на ограниченность использованного
нами подхода, при котором алгоритм на первом этапе независимо
находит два (пересекающихся по ребрам) максимальных цикловых
покрытия для весовых функций $w_1$ и $w_2$, а затем использует
эти покрытия для построения приближенного решения задачи
2-PSP-max-2W (2-APSP-max-2W). При этом в качестве верхней
границы для веса оптимального решения используется сумма
$w^*_1 + w^*_2$. Чтобы преодолеть это ограничение, мы
переходим к разработке приближенного алгоритма для задачи
2-CC-max-2W, который находит в графе два {\it реберно
неперсекающихся} цикловых покрытия $C_1$ и $C_2$, и к
разработке основанного на аналогичных идеях алгоритма
для задачи 2-PSP-max-2W с оценкой точности, превышающей $1/2$.

\section{Алгоритм $A_{2/3-\varepsilon}$ для задачи 2-CC-max-2W}

В этом разделе через $C^*_{1}$ и $C^*_{2}$ обозначаются два
реберно непересекающихся цикловых покрытия во входном графе $G$,
составляющие оптимальное решение задачи 2-CC-max-2W. Положим
$c^*_1 = w_1(C^*_{1})$ и $c^*_2 = w_2(C^*_{2})$. Тогда вес
оптимального решения задачи 2-CC-max-2W равен $c^*=c^*_1+c^*_2$.

В приведенном ниже алгоритме используется тот факт, что
полиномиальный алгоритм поиска циклового покрытия максимального
веса корректно работает не только для полного входного графа,
но и для произвольного.

\smallskip
Если $n\le 9$, то с помощью полного перебора находим в графе $G$
два реберно непересекающихся цикловых покрытия $C^*_{1},C^*_{2}$,
составляющие оптимальное решением задачи 2-CC-max-2W. Предположим,
что $n\ge 10$.

\smallskip
\textit{Этап 1.1.} Находим в графе $G$ цикловое покрытие $C_1$,
имеющее наибольший вес $w_1(C_1)$. Удаляем из $G$ все ребра
покрытия $C_1$, и в полученном графе $G \setminus C_1$ находим
цикловое покрытие $F_2$, имеющее наибольший вес $w_2(F_2)$.
В результате получаем пару реберно непересекающихся цикловых
покрытий $C_1,F_2$ в $G$, причем $w_1(C_1) \ge c^*_1$.

\smallskip
\textit{Этап 1.2.} Находим в $G$ цикловое покрытие $C_2$,
имеющее наибольший вес $w_2(C_2)$. Удаляем из $G$ все ребра
покрытия $C_2$, и в полученном графе $G \setminus C_2$ находим
цикловое покрытие $F_1$, имеющее наибольший вес $w_1(F_1)$.
Тем самым получаем пару реберно непересекающихся цикловых
покрытий $F_1,C_2$, причем $w_2(C_2) \ge c^*_2$.

\smallskip
\textit{Этап 2.} Формируем смешанный тур $K_1$, состоящий из всех
ребер циклового покрытия $C_2$, не принадлежащих $C_1$, и из всех
таких ребер $e \in  C_1 \cap C_2$, что $w_1(e) \ge w_2(e)$.
Аналогично формируем смешанный тур $K_2$, состоящий из всех
ребер покрытия $C_1$, не принадлежащих $C_2$ и из всех таких
ребер $e \in  C_1 \cap C_2$, что $w_2(e) > w_1(e)$. Из данного
определения следует, что $K_1$ и $K_2$ --- это два реберно
непересекающихся смешанных тура в $G$, где $K_1 \subseteq C_2$,
$K_2 \subseteq C_1$ и $K_1 \cup K_2 = C_1 \cup C_2$. Также
нетрудно понять, что пара туров $K_1,K_2$ обладает наибольшим
реберным весом $w_1(K_1)+w_2(K_2)$ среди всех таких пар реберно
непересекающихся смешанных туров, что первый из них целиком
содержится в $C_2$, а второй --- в $C_1$.

\smallskip
\textit{Этап 3.} Применяя процедуру, описанную в разделе 6.1,
преобразуем смешанный тур $K_1$ в цикловое покрытие $Z_1$,
не содержащее ребер тура $K_2$ и имеющее вес $w_1(Z_1) \ge
\left ( 1-\frac 3{n-3} \right ) w_1(K_1)$. Далее с помощью
той же процедуры преобразуем тур $K_2$ в цикловое покрытие
$Z_2$, не содержащее ребер из уже построенного покрытия $Z_1$
и имкющее вес $w_2(Z_2) \ge \left ( 1-\frac 3{n-3} \right )
w_2(K_2)$.

\smallskip
\textit{Этап 4.} Обозначим через $(J_1,J_2)$ ту из пар реберно
непересекающихся цикловых покрытий $(C_1,F_2)$, $(F_1,C_2)$,
$(Z_1,Z_2)$, которая имеет наибольший вес $w_1(J_1)+w_2(J_2)$.
Предъявляем пару цикловых покрытий $(J_1,J_2)$ в качестве
искомого приближенного решения задачи 2-CC-max-2W.

\medskip
Основным результатом данного раздела статьи является следующая

\medskip
{\bf Теорема 3.} {\em Представлннный выше алгоритм
$A_{2/3-\varepsilon}$ находит в полном взвшенном графе $G=G(V,E,
w_1,w_2)$ два реберно непересекающихся цикловых покрытия
$J_{1},\:J_{2}$, для веса которых выполняется неравенство
$w_1(J_{1})+w_2(J_{2}) \ge \left ( \frac 23 -\frac 1{n-3} \right )
c^*$. Время работы алгоритма $A_{2/3-\varepsilon}$ оценивается
как $O(n^3)$, где $n$ --- число вершин графа $G$.}

\medskip
Доказательство этой теоремы приводится в разделе 6.2.

\subsection{Преобразование смешанных туров в реберно
непересекающиеся цикловые покрытия} ~\\
Описанная в этом разделе процедура получает на вход два реберно
непересекающихся смешанных тура $K_1$ и $K_2$ (в частности,
любой из этих туров может быть цикловым покрытием в $G$) и
преобразует тур $K_1$ в цикловое покрытие $Z_1$, не имеющее
общих ребер с $K_2$ и такое, что $w_1(Z_1) \ge \left (
1-\frac 3{n-3} \right ) w_1(K_1)$. Процедура корректно работает
при условии $n \ge 10$.

\medskip
Далее нам понадобится следующая

\medskip
{\bf Лемма 3.} {\em Пусть $T$ --- смешанный тур во взвешенном
графе $G=(V,E,w)$. Если тур $T$ содержит $t \ge 6$ ребер, то
в $T$ найдутся также два несмежных ребра $e$ и $e'$, что
$w(e)+w(e') \le 2w(T)/t$.}

\smallskip
{\it Доказательство.} Рассмотрим вспомогательный граф $L$,
вершинами которого являются все ребра тура $T$, при этом в графе $L$
две вершины смежны, если соответствующие им ребра тура $T$ несмежны
в $G$ (иными словами $L$ --- это дополнение реберного графа $L(T)$
тура $T$). Так как каждое ребро тура $T$ смежно не более чем с двумя
другими ребрами из $T$, то степень каждой вершины графа $L$ не меньше
$(t-1)-2=t-3$. Поскольку $t-3 \ge t/2$ при $t \ge 6$, по теореме
Дирака (см. разд. 10 в \cite{Diestel}) граф $L$ содержит гамильтонов
цикл $H=(e_1,e_2,\ldots,e_t,e_1)$. Рассмотрим в туре $T$ пары
несмежных ребер $(e_1,e_2),(e_2,e_3),\ldots,(e_{t-1},e_t),(e_t,e_1)$.
Поскольку суммарный вес ребер во всех этих парах равен $2(w(e_1)+
w(e_2)+\ldots +w(e_t))=2w(T)$, то выбирая в качестве $(e,e')$
ту из указанных пар ребер, которая имеет наименьший вес, получаем
искомую оценку $w(e)+w(e') \le 2w(T)/t$. \, Лемма 3 доказана.

\medskip
Для каждой вершины $x \in V$ обозначим через $K_i(x)$ множество
всех ребер тура $K_i$, инцидентных вершине $x$. Ясно, что
$|K_i(x)| \le 2$. Будем полагать $K_i(x) = \emptyset$, если
в графе $G$ отсутствует вершина $x$.

\medskip
Приступим к описанию процедуры. Если смешанный тур $K_1$
состоит только из циклов, то он является искомым цикловым
покрытием $Z_1$. Предположим, что $K_1$ содержит хотя бы одну
цепь. Рассмотим следующие случаи.

\medskip
{\it Случай 1.} Тур $K_1$ содержит ровно одну цепь $P= u_1,u_2,
\ldots ,u_k$ (здесь и далее в обозначениях для цепи указывается
только последовательность ее вершин). Тогда $|K_1| = n-1$.
Если $k \ge 3$ и ребро $u_1u_k$ не принадлежит туру $K_2$,
то, добавляя это ребро к туру $K_1$, получим искомое цикловое
покрытие $Z_1$.

Пусть $k \ge 3$ и $u_1u_k \in K_2$. Существует не более одной
такой вершины $x \in V$, что оба ребра $xu_1$ и $xu_k$ принадлежат
туру $K_2$ (в этом случае в $K_2$ имеется цикл $(x,u_1,u_k,x)$
длины 3). Положим $R = K_1(x) \cup \{ u_1u_2,u_2u_3,u_{k-2}u_{k-1},
u_{k-1}u_k \}$ --- это подмножество ребер тура $K_1$ мощности не
более 6. Тогда $|K_1 \setminus R| \ge n-7$. Выберем во множестве
$K_1 \setminus R$ ребро $e=yz$ наименьшего веса. Тогда $w_1(e)
\le w_1(K_1)/(n-7)$. Удалим ребро $e$ из тура $K_1$. Тогда
полученный тур $K_1-e$ содержит ровно две цепи, концевыми
вершинами которых являются $u_1,u_k,y,z$ в каком-то порядке.
Из условий $e \not\in R$ и $u_1u_k \in K_2$ следует, что все
вершины $u_1,u_k,y,z$ попарно различны, тур $K_1$ не содержит
ни одного из ребер $yu_1,yu_k,zu_1,zu_k$ и хотя бы одна пара ребер
$yu_1,zu_k$ или $yu_k,zu_1$ не содержит ребра из $K_2$. Добавляя
эту пару ребер к туру $K_1-e$, получаем искомое цикловое покрытие
$Z_1$ веса $w_1(Z_1) \ge w_1(K_1) - w_1(e) \ge \left ( 1-\frac
1{n-7} \right ) w_1(K_1) \ge \left ( 1-\frac 3{n-3} \right )
w_1(K_1)$.

Пусть $k=2$. Определим множество ребер $R$, состоящее из ребра
$u_1u_2$ и все таких ребер $uv \in K_1$, что в туре $K_2$
имеется хотя бы два ребра, соединяющих вершины из $\{ u,v \}$
c вершинами из $\{ u_1,u_2 \}$. Так как в турах $K_1$ и $K_2$
каждая вершина имеет степень не больше 2, то $|R| \le 5$.
Тогда $|K_1 \setminus R| \ge n-6$. Выберем во множестве
$K_1 \setminus R$ ребро $e=yz$ наименьшего веса
$w_1(e) \le w_1(K_1)/(n-6)$. Удалим ребро $e$ из тура $K_1$.
Полученный тур $K_1-e$ содержит ровно две цепи, одной из
которых является $P=u_1u_2$, а вторая цепь получается из
какого-то цикла тура $K_1$ удалением ребра $e=yz$. Из условия
$e \not\in R$ следует, что тур $K_1$ не содержит ни одного из
ребер $yu_1,yu_2,zu_1,zu_2$ и хотя бы одна пара ребер $yu_1,
zu_2$ или $yu_2,zu_1$ не включает ребер из $K_2$. Добавляя
эту пару ребер к туру $K_1-e$, получаем искомое цикловое
покрытие $Z_1$ веса $w_1(Z_1) \ge w_1(K_1) - w_1(e) \ge
\left ( 1-\frac 1{n-6} \right ) w_1(K_1) \ge \left ( 1-\frac
3{n-3} \right ) w_1(K_1)$.

Пусть $k=1$, то есть цепь $P=u_1$ является синглом в $K_1$.
Существует не более двух вершин $x_1,x_2 \in V$, смежных
в туре $K_2$ с вершиной $v_1$. Положим $R = K_1(x_2) \cup
K_1(x_2)$ --- это подмножество ребер тура $K_1$ мощности
не более 4. Тогда $|K_1 \setminus R| \ge n-5$. Выберем во
множестве $K_1 \setminus R$ ребро $e=yz$ наименьшего веса
$w_1(e) \le w_1(K_1)/(n-5)$. Тогда тур $K_1-e$ содержит
ровно две цепи, одной из которых является $P=u_1$, а вторая
цепь получается из какого-то цикла в $K_1$ удалением ребра
$e=yz$. Из условия $e \not\in R$ следует, что никакое
из ребер $yu_1,zu_1$ не принадлежит ни одному из туров
$K_1,K_2$. Добавляя ребра $yu_1$ и $zu_1$ к туру $K_1-e$,
получаем искомое цикловое покрытие $Z_1$ веса $w_1(Z_1)
\ge w_1(K_1) - w_1(e) \ge \left ( 1-\frac 1{n-5} \right )
w_1(K_1) \ge \left ( 1-\frac 3{n-3} \right ) w_1(K_1)$.

\medskip
{\it Случай 2.} $p(K_1)=2$, то есть тур $K_1$ содержит
две цепи $P_1 = u_1,u_2,\ldots ,u_k$ и $P_2 = v_1,v_2,
\ldots ,v_l$. Тогда $|K_1| = n-2$. Если хотя бы одно из
ребер $u_1v_1,u_1v_l,u_kv_1,u_kv_l$ не принадлежит туру
$K_2$, то добавим это ребро к туру $K_1$. В результате
получим смешанный тур веса не меньше $w_1(K_1)$, содержащий
ровно одну цепь. Преобразуем этот тур в цикловое покрытие
$Z_1$, как описано в Случае 1. Далее будем считать, что
все ребра $u_1v_1,u_1v_l,u_kv_1,u_kv_l$ принадлежат туру
$K_2$. Если $k\ge 3$ и ребро $u_1u_k$ не принадлежит $K_2$,
то добавляя это ребро к туру $K_1$ и переходя к Случаю 1,
получим искомое цикловое покрытие $Z_1$. Аналогинчо
рассматривается случай, когда $l\ge 3$ и $v_1v_l \not\in
K_2$. Поскольку в туре $K_2$ каждая из вершин $u_1,
u_k,v_1,v_l$ имеет степень не больше 2, то остается
рассмотреть только следующме два подслучая.

\smallskip
{\it Случай 2.1.} Одна из цепей $P_1$ или $P_2$ является
синглом в $K_1$. Можно считать, что $P_2 = v_1$. В этом
случае $u_1v_1 \in K_2$, $u_kv_1 \in K_2$ и если $k \ge 3$,
то $u_1u_k \in K_2$. При $k \ge 2$ полагаем $R=\{ u_1u_2,
u_{k-1}u_k \}$, а при $k=1$ выберем такую вершину $x\in
V \setminus \{ u_1,v_1 \}$, что $xu_1 \in K_2$ и $xv_1
\in K_2$, и положим $R = K_1(x)$ (если такая вершина $x$
существует, то она единственна). В обоих случаях имеем
$|R| \le 2$ и $|K_1 \setminus R| \ge n-4 \ge 6$.

По лемме 3 смешанный тур $K_1 \setminus R$ содержит такие
два несмежных ребра $e_1 = y_1z_1$ и $e_2 = y_2z_2$, что
$w_1(e_1)+w_1(e_2) \le \frac 2{n-4} w_1(K_1 \setminus R)
\le \frac 2{n-4} w_1(K_1)$. Удалим из $K_1$ ребра $e_1$
и $e_2$. Так как они несмежны между собой, то все вершины
$y_1,y_2,z_1,z_2$ попарно различны. При этом из определения
множества $R$ и условия $e_1,e_2 \not\in R$ следует, что
$\{ y_1,y_2,z_1,z_2 \} \cap \{ u_1,u_k,v_1 \} = \emptyset$.
Если $k\ge 2$, то в туре $K_2$ вершинна $v_1$ несмежна с
вершинами из множества $\{ y_1,y_2,z_1,z_2 \}$, а каждая
из вершин $u_1$, $u_k$ смежна не более чем с одной вершиной
из этого множества (поскольку $u_1v_1 \in K_2$ и $u_kv_1
\in K_2$). Без потери общности будем считать, что в туре
$K_2$ вершины $u_1$ и $u_k$ несмежны с вершинами $y_1$ и
$y_2$ соответственно. Добавляя к туру $K_1 \setminus
\{ e_1,e_2 \}$ ребра $u_1y_1,u_ky_2,v_1z_1,v_1z_2$,
получаем искомое цикловое покрытие $Z_1$ веса $w_1(Z_1)
\ge w_1(K_1) - (w_1(e_1) + w_1(e_2)) \ge \left ( 1-\frac
2{n-4} \right ) w_1(K_1) \ge \left ( 1-\frac 3{n-3}
\right ) w_1(K_1)$. Пусть $k=1$. Тогда $u_1v_1 \in K_2$
и в туре $K_2$ каждая из вершин $u_1,v_1$ смежна не более
чем с одной вершиной из множества $\{ y_1,y_2,z_1,z_2 \}$.
Так как $e_1,e_2 \not\in R$, то ни одна из вершин $y_1,
y_2.z_1,z_2$ не может быть смежна в $K_2$ одновременно
с обеими вершинами $u_1$ и $v_1$. Поэтому можно считать,
что в туре $K_2$ вершина $u_1$ смежна только с $v_1$ и
$y_1$, а $v_1$ смежна только с $u_1$ и $y_2$. Добавляя
к туру $K_1 \setminus \{ e_1,e_2 \}$ ребра $u_1y_2,
u_1z_2,v_1y_1,v_1z_1$, получаем искомое цикловое
покрытие $Z_1$ веса $w_1(Z_1) \ge \left ( 1-\frac
2{n-4} \right ) w_1(K_1) \ge \left ( 1-\frac 3{n-3}
\right ) w_1(K_1)$.

\smallskip
{\it Случай 2.2.} $k=l=2$, то есть $P_1=u_1u_2$, $P_2=
v_1v_2$. При этом ребра $u_1v_1,u_1v_2,u_2v_1,$ $u_2v_2$
принадлежат туру $K_2$. Это означает, что в туре $K_2$
имеется цикл $(u_1,v_1,u_2,v_2,u_1)$ длины 4. По лемме 3
смешанный тур $K_1 \setminus \{ u_1v_1,u_2v_2 \}$ содержит
такие два несмежных ребра $e_1 = y_1z_1$ и $e_2 = y_2z_2$,
что $w_1(e_1)+w_1(e_2) \le \frac 2{n-4} w_1(K_1 \setminus
\{ u_1v_1,u_2v_2 \}) \le \frac 2{n-4} w_1(K_1)$. Удалим
из тура $K_1$ ребра $e_1$ и $e_2$. Так как ни одно из этих
ребер не принадлежит множеству $\{ u_1v_1,u_2v_2 \}$, то
$\{ y_1,y_2,z_1,z_2 \} \cap \{ u_1,u_2,v_1,v_2 \} =
\emptyset$. Из наличия в туре $K_2$ цикла $(u_1,v_1,u_2,
v_2,u_1)$ следует, что ни одна из вершин $u_1,u_2,v_1,v_2$
не смежна в $K_2$ с вершинами из множества $\{ y_1,y_2,z_1,
z_2 \}$. Добавляя к туру $K_1 \setminus \{ e_1,e_2 \}$
ребра $u_1y_1,u_2z_1,v_1y_2,v_2z_2$, получим искомое
цикловое покрытие $Z_1$ веса $w_1(Z_1) \ge \left (
1-\frac 2{n-4} \right ) w_1(K_1) \ge \left ( 1-\frac
3{n-3} \right ) w_1(K_1)$.

\medskip
{\it Случай 3.} $p(K_1)=3$, то есть тур $K_1$ содержит
три цепи $P_1 = u_1,u_2,\ldots ,u_k$, $P_2 = v_1,v_2,
\ldots ,v_l$ и $P_3 = w_1,w_2,\ldots ,w_m$. Тогда $|K_1|
= n-3$. Если хотя бы одно из чисел $k,l,m$ не равно 1,
скажем, $m>1$, то какое-то из ребер $u_1v_1,u_1w_1,
u_1w_m$ не принадлежит туру $K_2$. Добавляя это ребро
к туру $K_1$, получаем смешанный тур, содержащий ровно
две цепи, после чего переходим к Случаю 2.

Пусть $k=l=m=1$. Тогда все три цепи тура $K_1$ являются
синглами, а в туре $K_2$ имеется цикл $(u_1,v_1.w_1,u_1)$
длины 3 (иначе снова можно перейти к Случаю 2). Удалим из
тура $K_1$ три ребра $e_1 = y_1z_1$, $e_2 = y_2z_2$ и
$e_3 = y_3z_3$ наименьшего веса (сейчас мы допускаем, что
среди этих ребер могут быть смежные, то есть среди вершин
$y_1,z_1,y_2,z_2,y_3,z_3$ могут быть повторяющиеся).
Тогда $w_1(e_1)+w_1(e_2)+w_1(e_3) \le \frac 3{n-3}
w_1(K_1)$. Добавляя к туру $K_1 \setminus \{ e_1,e_2,e_3
\}$ ребра $u_1y_1,u_1z_1,v_1y_2,v_1z_2,w_1y_3,w_1z_3$,
получим искомое цикловое покрытие $Z_1$ веса $w_1(Z_1)
\ge \left ( 1-\frac 3{n-3} \right ) w_1(K_1)$.

\medskip
{\it Случай 4.} $p(K_1) \ge 4$, то есть тур $K_1$ содержит
не менее четырех цепей. В этом случае среди ребер графа $G$,
соединяющих концы различных цепей тура $K_1$, найдется ребро,
не принадлежащее туру $K_2$. Добавим это ребро к туру $K_1$.
Будем действовать так до тех пор, пока в $K_1$ не останется
ровно три цепи. После этого перейдем к Случаю 3.

\medskip
Нетрудно убедиться, что время работы описанной процедуры
преобразования смешанного тура $K_1$ в цикловое покрытие
$Z_1$ не превосходит $O(n^2)$.

\subsection{Доказательство теоремы 3} ~\\
Трудоемкость алгоритма $A_{2/3-\varepsilon}$ определяется
временем отыскания цикловых покрытий $C_1,C_2,F_1,F_2$ на
Этапах 1.1 и 1.2, которое оценивается как $O(n^3)$.

Докажем оценку точности $\frac 23 - \frac 1{n-3}$. Рассмотрим
в графе $G$ пару реберно непересекающихся цикловых покрытий
$C^*_{1},C^*_{2}$, составляющих оптимальное решение задачи
2-CC-max-2W. Согласно ранее введенным обозначениям имеем
$c^*_1 = w_1(C^*_{1})$, $c^*_2 = w_2(C^*_{2})$ и $c^* =
c^*_1+c^*_2$ --- это оптимум задачи 2-CC-max-2W. Тогда для
найденных алгоритмом на Этапах 1.1 и 1.2 цикловых покрытий
$C_1$ и $C_2$ справедливы оценки $w_i(C_i) \ge c^*_i$,
$i=1,2$.

Определим следующие множества ребер (смешанные туры) в $G$:
$X_1 = C^*_{1} \setminus C_2$; $Y_1 = C^*_{1} \cap C_2$;
$X_2 = C^*_{2} \setminus C_1$; $Y_2 = C^*_{2} \cap C_1$.
Тогда для каждого $i=1,2$ множества $X_i$ и $Y_i$ образуют
разбиение множества ребер циклового покрытия $C^*_i$, что
влечет равенства $w_i(X_i)+w_i(Y_i) = c^*_i$, $i=1,2$.

Заметим, что множество ребер $X_1$ представляет из себя
смешанный тур в графе $G \setminus C_2$, а построенное
на Этапе 1.2 алгоритма цикловое покрытие $F_1$ также
содержится в этом графе и имеет в нем наибольший вес
$w_1(F_1)$. Так как смешанный тур $X_1$ с помощью
процедуры, описанной в разделе 6.1, можно преобразовать
в цикловое покрытие $F'_1$, реберно непересекающееся с
$C_2$ (то есть содержащееся в графе $G \setminus C_2$)
и имеющее вес $w_1(F'_1) \ge \left ( 1-\frac 3{n-3}
\right ) w_1(X_1)$, то для веса максимального циклового
покрытия $F_1$ в $G \setminus C_2$ выполняется оценка
$w_1(F_1) \ge w_1(F'_1) \ge \left ( 1-\frac 3{n-3}
\right ) w_1(X_1)$. Аналогично доказывается, что
$w_2(F_2) \ge \left ( 1-\frac 3{n-3} \right ) w_2(X_2)$.

Из определения смешаннх туров $Y_1$ и $Y_2$ следует,
что они не имеют общих ребер, так как первый из них
содержатся в цикловом покрытии $C^*_1$, а второй
--- в $C^*_2$, где $C^*_1 \cap C^*_2 = \emptyset$.
Кроме того, тур $Y_1$ содержится в цикловом покрытии
$C_2$, а тур $Y_2$ --- в $C_1$. На Этапе 2 алгоритма
было установлено, что определенная на этом этапе пара
смешанных туров $K_1,K_2$ имеет наибольший вес
$w_1(K_1)+w_2(K_2)$ среди всех таких пар реберно
непересекающихся смешанных туров, что первый из них
содержится в $C_2$, а второй --- в $C_1$. Отсюда
следует, что $w_1(K_1)+w_2(K_2) \ge w_1(Y_1)+w_2(Y_2)$.
Поэтому для построенных на Этапе 3 цикловых покрытий
$Z_1$ и $Z_2$ справедлива оценка $w_1(Z_1)+w_2(Z_2) \ge
\left ( 1-\frac 3{n-3} \right ) (w_1(K_1)+w_2(K_2))
\ge \left ( 1-\frac 3{n-3} \right ) (w_1(Y_1)+w_2(Y_2))$.

Предположим, что заявленная оценка точности алгоритма
$A_{2/3-\varepsilon}$ неверна. Тогда для построенных
на Этапе 4 цикловых покрытий $J_1$ и $J_2$
справедливо неравенство $w_1(J_1)+w_2(J_2) < \left (
\frac 23 - \frac 1{n-3} \right ) c^*$. Из определения
покрытий $J_1$ и $J_2$, следует, что $w_1(C_1)+w_2(F_2)
< \left ( \frac 23 - \frac 1{n-3} \right ) c^*$,
$w_1(F_1)+w_2(C_2) < \left ( \frac 23 - \frac 1{n-3}
\right ) c^*$ и $w_1(Z_1)+w_2(Z_2) < \left ( \frac 23
- \frac 1{n-3} \right ) c^*$. Складывая последние три
неравенства и используя ранее полученные соотношения,
приходим к следующей цепочке неравенств:
$$\left ( 2 - \frac 3{n-3} \right ) c^* > (w_1(C_1)+
w_2(C_2)) + (w_1(F_1)+w_2(F_2)) + (w_1(Z_1)+w_2(Z_2)) \ge$$
$$(c^*_1+c^*_2) + \left ( 1-\frac 3{n-3} \right )
(w_1(X_1)+w_2(X_2)) + \left ( 1-\frac 3{n-3} \right )
(w_1(Y_1)+w_2(Y_2)) =$$
$$c^* + \left ( 1-\frac 3{n-3}
\right ) (w_1(X_1)+w_1(Y_1))+w_2(X_2)+w_2(Y_2)) =$$
$$c^* + \left ( 1-\frac 3{n-3} \right ) (c^*_1+c^*_2)
= c^* + \left ( 1-\frac 3{n-3} \right ) c^* =
\left ( 2 - \frac 3{n-3} \right ) c^*.$$
Из полученного противоречия следует, что $w_1(J_1)+
w_2(J_2) \ge \left ( \frac 23 - \frac 1{n-3} \right )
c^*$, то есть заявленная оценка точности
$\frac 23 - \frac 1{n-3}$ верна. \, Теорема 3 доказана.

\section{Алгоритм $A_{>1/2}$ для задачи 2-PSP-max-2W}

В этом разделе, как и в разделе 3, через $H^*_{1},H^*_{2}$
обозначается пара реберно непересекающихся гамильтоновых циклов,
составляющих оптимальное решение задачи 2-PSP-max-2W. Положим
$w_i^* = w_i(H^*_{i})$, $i=1,2$; $w^* = w_1^*+w_2^*$. Для
каждого гамильтонова цикла $C$ в $G$ обозначим через $w_i^C$
весовую функцию ребер, которая совпадает с $w_i$ на всех ребрах
не из цикла $C$ и равна нулю на всех ребоах из $C$. Назовем
{\it про-туром} любой частичный тур или гамильтонов цикл в $G$.

В представленном ниже алгоритме $A_{>1/2}$ в качестве вспомогательной
процедуры может использоваться любой известный полиномиальный алгоритм $A'$
для задачи одного коммивояжера на максимум, обладающий гарантированной
оценкой точности $L > 2/3$. Примером такого алгоритма может служить
разработанный Сердюковым \cite{Serd}  алгоритм с оценкой точности
$3/4$, а наилучшей на сегодня оценкой $4/5$ обладает алгоритм из
\cite{DMPR}. Трудоемкость этих и многих других приближенных алгоритмов
для задачи TSP-max оценивается как $O(n^3)$. При этом важно отметить,
что большинство этих алгоритмов корректно работает лишь при условии,
что входной граф $G$ является полным. Это не позволяет применить
подход, ранее использованный в алгоритме $A_{2/3-\varepsilon}$,
при котором цикловое покрытие максимального веса находилось в графе,
из которого были удалены ребра другого циклового покрытия. Вместо
этого в предложенном здесь алгоритме $A_{>1/2}$ обнуляются веса ребер,
принадлежащих некоторому гамильтонову циклу, однако сами эти ребра
не удаляются из графа. Оценка точности алгоритма $A_{>1/2}$ является
асимптотической, со значениями в пределах от $1/2$ до $4/7$, и зависит
от оценки $L$ алгоритма $A'$ для задачи TSP-max (точное значение оценки
точности приводится ниже в теореме 4).

\medskip
Приступим к описанию алгоритма $A_{>1/2}$. Если $n\le 5$, то с помощью
полного перебора находим в графе $G$ два реберно непересекающихся
гамильтонова цикла $H^*_{1},H^*_{2}$, составляющие оптимальное решение
задачи 2-PSP-max-2W. Предположим, что $n\ge 6$.

\smallskip
\textit{Этап 1.1.} Применяя $L$-приближенный алгоритм $A'$ для задачи
TSP-max к графу $G$ с весовой функцией $w_1$, находим в $G$ гамильтонов
цикл $C_1$, имеющий вес $w_1(C_1) \ge Lw_1^*$. Далее применяя тот же
алгоритм к графу $G$ c весовой функцией $w_2^{C_1}$, находим гамильтонов
цикл $F'_2$. Если циклы $C_1$ и $F'_2$ не имеют общих ребер, то полагаем
$F_2=F'_2$ и переходим на Этап 2. Иначе удаляем из $F'_2$ все ребра цикла
$C_1$ и получаем частичный тур $T_2 = F'_2 \setminus C_1$, реберно
непересекающийся с $C_1$ и имеющий вес $w_2(T_2) = w_2^{C_1}(F'_2)$.
Применяя к туру $T_2$ процедуру из раздела 7.1, преобразуем $T_2$ в
гамильтонов цикл $F_2$, не содержащий ребер из $C_1$ и имеющий вес
$w_2(F_2) \ge \left ( 1-\frac 1{n-5} \right ) w_2(T_2) = \left (
1-\frac 1{n-5} \right ) w_2^{C_1}(F'_2)$.

\smallskip
\textit{Этап 1.2.} Применяя алгоритм $A'$ к графу $G$ с весовой функцией
$w_2$, находим в $G$ гамильтонов цикл $C_2$ веса $w_2(C_2) \ge Lw_2^*$.
Далее применяя тот же алгоритм к графу $G$ c весовой функцией $w_1^{C_2}$,
находим гамильтонов цикл $F'_1$. Если циклы $C_2$ и $F'_1$ не имеют общих
ребер, то полагаем $F_1=F'_1$ и переходим на Этап 2. Иначе формируем
частичный тур $T_1 = F'_1 \setminus C_2$, реберно непересекающийся с $C_2$
и имеющий вес $w_1(T_1) = w_1^{C_2}(F'_1)$. С помощью процедуры из раздела
7.1 преобразуем тур $T_1$ в гамильтонов цикл $F_1$, не содержащий ребер из
$C_2$ и имеющий вес $w_1(F_1) \ge \left ( 1-\frac 1{n-5} \right ) w_1(T_1)
= \left ( 1-\frac 1{n-5} \right ) w_1^{C_2}(F'_1)$.

\smallskip
\textit{Этап 2.}  Формируем про-тур $K_1$, состоящий из всех ребер
гамильтонова цикла $C_2$, не принадлежащих циклу $C_1$, и из всех
таких ребер $e \in  C_1 \cap C_2$, что $w_1(e) \ge w_2(e)$.
Аналогично формируем про-тур $K_2$, состоящий из всех ребер цикла
$C_1$, не принадлежащих $C_2$ и из всех таких ребер $e \in  C_1
\cap C_2$, что $w_2(e) > w_1(e)$. Тогда про-туры $K_1$ и $K_2$
не имеют общих ребер, при этом $K_1 \subseteq C_2$, $K_2 \subseteq
C_1$ и $K_1 \cup K_2 = C_1 \cup C_2$. Ясно, что пара про-туров
$K_1,K_2$ обладает наибольшим весом $w_1(K_1)+w_2(K_2)$ среди всех
таких пар реберно непересекающихся про-туров, что первый из них
содержится в $C_2$, а второй --- в $C_1$.

\smallskip
\textit{Этап 3.} С помощтю процедуры из раздела 7.1 преобразуем
про-тур $K_1$ в гамильтонов цикл $Z_1$, не содержащий ребер из
$K_2$ и имеющий вес $w_1(Z_1) \ge \left ( 1-\frac 1{n-5} \right )
w_1(K_1)$. Далее с помощью той же процедуры преобразуем про-тур
$K_2$ в гамильтонов цикл $Z_2$, не содержащий ребер из уже
построенного цикла $Z_1$ и имкющий вес $w_2(Z_2) \ge \left (
1-\frac 1{n-5} \right )w_2(K_2)$.

\smallskip
\textit{Этап 4.} Обозначим через $(H_1,H_2)$ ту из пар реберно
непересекающихся гамильтоновых циклов $(C_1,F_2)$, $(F_1,C_2)$,
$(Z_1,Z_2)$, которая имеет наибольший вес $w_1(H_1)+w_2(H_2)$.
Предъявляем пару циклов $(H_1,H_2)$ в качестве искомого
приближенного решения задачи 2-PSP-max-2W.

\medskip
Основным результатом данного раздела является следующая

\medskip
{\bf Теорема 4.} {\em Представлннный выше алгоритм $A_{>1/2}$
находит в полном взвшенном графе $G=G(V,E,w_1,w_2)$ два реберно
непересекающихся гамильтоновых цикла $H_{1},\:H_{2}$, для которых
выполняется неравенство $w_1(H_{1})+w_2(H_{2}) \ge \frac {2L}{2+L}
\left ( 1 -\frac 1{n-5} \right ) w^*$, где $L$ --- оценка точности
алгоритма $A'$, применяемого на Этапах 1.1. и 1.2.  Время работы
алгоритма $A_{>1/2}$ оценивается как $O(n^3)$, где $n$ --- число
вершин графа $G$.}

\medskip
Доказательство этой теоремы приводится в разделе 7.2.

\subsection{Преобразование про-туров в реберно непересекающиеся
гамильтоновы циклы} ~\\
Описанная в этом разделе процедура получает на вход два реберно
непересекающихся про-тура $K_1$ и $K_2$ (любой из них может быть
гамильтоновым циклом) и преобразует про-тур $K_1$ в гамильтонов
цикл $Z_1$, не имеющий общих ребер с $K_2$ и такой, что $w_1(Z_1)
\ge \left ( 1-\frac 1{n-5} \right ) w_1(K_1)$. Процедура корректно
работает при условии $n \ge 6$.

\medskip
Если про-тур $K_1$ является гамильтоновым циклом, то полагаем
$Z_1=K_1$ и завершаем работу. Пусть $K_1$ является частичным
туром в $G$. Рассмотим следующие случаи.

\medskip
{\it Случай 1.} Тур $K_1$ соcтоит из единственной (гамильтоновой)
цепи $P= u_1,u_2,\ldots,u_n$. Тогда $|K_1| = n-1$. Если ребро
$u_1u_n$ не принадлежит про-туру $K_2$, то, добавляя это ребро
к $K_1$, получаем искомый гамильтонов цикл $Z_1$.

Пусть $u_1u_n \in K_2$. Тогда существует не более одной такой
вершины $u_i \in V \setminus \{ u_1,u_n \}$, что ребро $u_1u_i$
принадлежит про-туру $K_2$, и cуществует не более одной такой
вершины $u_j \in V \setminus \{ u_1,u_n \}$, что $u_nu_j \in K_2$.
Положим $R = \{ u_1u_2, u_{n-1}u_n, u_{i-1}u_i, u_ju_{j+1} \}$
--- это подмножество ребер тура $K_1$ мощности не более 4. Тогда
$|K_1 \setminus R| \ge n-5$. Выберем во множестве $K_1 \setminus
R$ ребро $e=u_{k-1}u_k$ наименьшего веса $w_1(e) \le w_1(K_1)/(n-5)$.
Удалим ребро $e$ из тура $K_1$. Полученный частичный тур $K_1-e$
состоит ровно из двух цепей: $P_1 =u_1,u_2,\ldots ,u_{k-1}$ и
$P_2 =u_k,u_{k+1},\ldots ,u_n$. Из условия $e \not\in R$ следует,
что все четыре вершины $u_1,u_{k-1},u_k,u_n$ попарно различны и
ни одно из ребер $u_1u_k, u_{k-1}u_n$ не принадлежит ни одному
из про-туров $K_1,K_2$. Добавляя эти два ребра к туру $K_1-e$,
получаем искомый гамильтонов цикл $Z_1$ веса $w_1(Z_1) \ge w_1(K_1)
- w_1(e) \ge \left ( 1-\frac 1{n-5} \right ) w_1(K_1)$.

\medskip
{\it Случай 2.} Тур $K_1$ соcтоит из двух цепей: $P_1=u_1,u_2,
\ldots,u_k$ и $P_2=v_1,v_2,\ldots,v_l$. Тогда $|K_1| = n-2$.
Если обе цепи $P_1$ и $P_2$ являются нетривиальными, то есть
$k\ge 2$, $l\ge 2$, то все вершины $u_1,u_k,v_1,v_l$ попарно
различны. Поскольку про-тур $K_2$ не может содержать цикл
$(u_1,v_1,u_k,v_l,u_1)$ длины 4, то хотя бы одно из ребер
$u_1v_1,u_1v_l,u_kv_1,u_kv_l$ не принадлежит $K_2$. Добавляя
это ребро к туру $K_1$, получаем частичный тур, состоящий ровно
из одной цепи, и переходим к Случаю 1.

Пусть какая-то из цепей $P_1$ или $P_2$, скажем $P_2$, является
синглом в $K_1$. Тогда $k=n-1$, $l=1$. Если хотя бы одно ребро
$u_1v_1$ или $u_{n-1}v_1$ не принадлежит $K_2$, то добавим это
ребро к туру $K_1$ и снова перейдем к Случаю 1. Пусть $u_1v_1,
u_{n-1}v_1 \in K_2$. Так как про-тур $K_2$ не может содержать
цикл $(u_1,v_1,u_{n-1},u_1)$, то $u_1u_{n-1} \not\in K_2$.
Также вершина $v_1$ несмежна в $K_2$ ни с одной вершиной
$u_2,u_3,\ldots,u_{n-2}$. Выберем во множестве $K_1 \setminus
\{ u_1u_2,u_{n-2}u_{n-1} \}$ ребро $e=u_{i-1}u_i$ наименьшего
веса $w_1(e)$. Так как $|K_1 \setminus\{ u_1u_2,u_{n-2}u_{n-1}
\}| = n-4$, то $w_1(e) \le w_1(K_1)/(n-4)$. Частичный тур $K_1-e$
состоит из трех цепей: $P'_1 = u_1,u_2,\ldots,u_{i-1}$, $P''_1 =
u_i,u_{i+1},\ldots,u_{n-1}$ и $P_2 = v_1$. При этом ни одно из
ребер $u_1u_{n-1},u_{i-1}v_1,u_iv_1$ не принадлежит ни одному
из про-туров $K_1,K_2$. Добавляя эти три ребра к туру $K_1-e$,
получаем искомый гамильтонов цикл $Z_1$ веса $w_1(Z_1) \ge
w_1(K_1) - w_1(e) \ge \left ( 1-\frac 1{n-4} \right ) w_1(K_1)
\ge \left ( 1-\frac 1{n-5} \right ) w_1(K_1)$.

\medskip
{\it Случай 3.} Тур $K_1$ содержит не менее трех цепей. Так как
в про-туре $K_2$ степень каждой вершины не превосходит 2, то среди
ребер графа $G$, соединяющих концы различных цепей тура $K_1$,
найдется ребро, не принадлежащее $K_2$. Добавим это ребро  к туру
$K_1$. Будем действовать так до тех пор, пока в $K_1$ не останется
ровно две цепи. После этого перейдем к Случаю 2.

\medskip
Нетрудно убедиться, что время работы описанной процедуры
преобразования про-тура $K_1$ в гамильтонов цикл $Z_1$ не
превосходит $O(n^2)$.

\subsection{Доказательство теоремы 4} ~\\
Трудоемкость алгоритма $A_{>1/2}$ определяется временем
работы $L$-приближенного алгоритм $A'$ для задачи TSP-max
на Этапах 1.1 и 1.2. Для большинства известных алгоритмов
это время оценивается как $O(n^3)$.

Докажем оценку точности $\frac {2L}{2+L} \left ( 1 -\frac
1{n-5} \right )$. Рассмотрим в графе $G$ пару реберно
непересекающихся гамильтоновых циклов $H^*_{1},H^*_{2}$,
составляющих оптимальное решение задачи 2-PSP-max-2W.
Тогда $w^*_1 = w_1(H^*_{1})$, $w^*_2 = w_2(H^*_{2})$ и
$w^* =w^*_1+w^*_2$ --- это оптимум задачи 2-PSP-max-2W.
Как было отмечено выше, для найденных алгоритмом $A'$
на Этапах 1.1 и 1.2 гамильтоновых циклов $C_1$ и $C_2$
выполняются оценки $w_i(C_i) \ge Lw^*_i  \ge L \left (
1 -\frac 1{n-5} \right ) w^*_i$, $i=1,2$.

Определим следующие множества ребер (про-туры) в $G$:
$X_1 = H^*_{1} \setminus C_2$; $Y_1 = H^*_{1} \cap C_2$;
$X_2 = H^*_{2} \setminus C_1$; $Y_2 = H^*_{2} \cap C_1$.
Для каждого $i=1,2$ множества $X_i$ и $Y_i$ образуют
разбиение множества ребер гамильтонова цикла $H^*_i$, а
значит, $w_i(X_i)+w_i(Y_i) = w^*_i$, $i=1,2$.
Рассмотрим в графе $G$ какой-нибудь гамильтонов цикл
$F''_1$, содержащий все ребра про-тура $X_1$. Так как
про-тур $X_1$ не содержит ребер гамильтонова цикла $C_2$,
то $w_1^{C_2}(F''_1) \ge w_1(X_1)$. Найденный на Этапе
1.2 гамильтонов цикл $F'_1$ получен $L$-приближенным
алгоритмом $A'$ с весовой функцией $w_1^{C_2}$, поэтому
$w_1^{C_2}(F'_1) \ge Lw_1^{C_2}(F''_1) \ge Lw_1(X_1)$.
Следовательно, для построенного к концу Этапа 1.2
гамильтонова цкла $F_1$ выполняется оценка $w_1(F_1)
\ge \left ( 1-\frac 1{n-5} \right ) w_1^{C_2}(F'_1) \ge
L \left ( 1-\frac 1{n-5} \right ) w_1(X_1)$. Аналогично
доказывается, что  $w_2(F_2) \ge L \left ( 1-\frac 1{n-5}
\right ) w_2(X_2)$. Отсюда и из доказанных выше неравенств
для $C_1$ и $C_2$ следует, что $w_1(C_1)+w_2(F_2) \ge
L \left ( 1 -\frac 1{n-5} \right ) (w^*_1 + w_2(X_2))$ и
$w_1(F_1)+w_2(C_2) \ge L \left ( 1 -\frac 1{n-5} \right )
(w^*_2 + w_1(X_1))$.

Из определения про-туров $Y_1$ и $Y_2$ следует, что они
не имеют общих ребер, так как первый из них содержится
в гамильтоновом цикле $H^*_1$, а второй --- в $H^*_2$,
где $H^*_1 \cap H^*_2 = \emptyset$. Кроме того, про-тур
$Y_1$ содержится в гамильтоновом цикле $C_2$, а про-тур
$Y_2$ --- в $C_1$. На Этапе 2 алгоритма было установлено,
что определенная на этом этапе пара про-туров $K_1,K_2$
имеет наибольший вес $w_1(K_1)+w_2(K_2)$ среди всех таких
пар реберно непересекающихся про-туров, что первый из них
содержится в $C_2$, а второй --- в $C_1$. Отсюда следует,
что $w_1(K_1)+w_2(K_2) \ge w_1(Y_1)+w_2(Y_2)$. Поэтому
для построенных на Этапе 3 гамильтоновых циклов $Z_1$ и
$Z_2$ справедлива оценка $w_1(Z_1)+w_2(Z_2) \ge \left (
1-\frac 1{n-5} \right ) (w_1(K_1)+w_2(K_2)) \ge \left (
1-\frac 1{n-5} \right ) (w_1(Y_1)+w_2(Y_2))$.

Предположим, что заявленная оценка точности алгоритма
$A_{>1/2}$ неверна. Тогда для построенных на Этапе 4
гамильтоновых циклов $H_1$ и $H_2$ выполняется
неравенство $w_1(H_1)+w_2(H_2) < \frac {2L}{2+L}
\left ( 1 - \frac 1{n-5} \right ) w^*$. Отсюда и из
ранее доказанных неравенств следует, что
$$\frac {2L}{2+L} \left ( 1 - \frac 1{n-5} \right )
w^* > w_1(C_1)+w_2(F_2)  \ge L \left ( 1 - \frac 1{n-5}
\right ) (w^*_1 + w_2(X_2));$$
$$\frac {2L}{2+L} \left ( 1 - \frac 1{n-5} \right )
w^* > w_1(F_1)+w_2(C_2)  \ge L \left ( 1 - \frac 1{n-5}
\right ) (w^*_2 + w_1(X_1));$$
$$\frac {2L}{2+L} \left ( 1 - \frac 1{n-5} \right )
w^* > w_1(Z_1)+w_2(Z_2)  \ge \left ( 1 - \frac 1{n-5}
\right ) (w_1(Y_1)+w_2(Y_2)).$$
Следовательно,
$$w^*_1 + w_2(X_2) < \frac {2}{2+L} w^*; \quad
w^*_2 + w_1(X_1) < \frac {2}{2+L} w^*; \quad
w_1(Y_1)+w_2(Y_2) <  \frac {2L}{2+L} w^*.$$
Отсюда получаем,  что
$$2w^* = w^*_1 + w^*_2 + w^*_1 + w^*_2 = w^*_1 + w^*_2
+ (w_1(X_1) + w_1(Y_1)) + (w_2(X_2) + w_2(Y_2)) =$$
$$(w^*_1 + w_2(X_2)) + (w^*_2 + w_1(X_1)) + (w_1(Y_1)
+w_2(Y_2)) < \left ( \frac {2}{2+L} + \frac {2}{2+L} +
\frac {2L}{2+L} \right ) w^* = 2w^*.$$
Из полученного противоречия следует, что $w_1(H_1)+
w_2(H_2) \ge \frac {2L}{2+L} \left ( 1 - \frac 1{n-5}
\right ) w^*$, то есть заявленная оценка точности
$\frac {2L}{2+L} \left ( 1 - \frac 1{n-5}
\right )$ верна. \, Теорема 4 доказана.

\medskip
В заключение заметим, что если на Этапах 1.1 и 1.2 алгоритма
$A_{>1/2}$ в качестве вспомогательного $L$-приближенного
алгоритма $A'$ для задачи TSP-max используeтся простейший
алгоритм с оценкой точности $L=2/3$, то главный член $\frac
{2L}{2+L}$ оценки точности алгоритма $A_{>1/2}$ принимает
значение $1/2$, что соответствует оценке алгоритма $A_{1/2}$,
описанного в разделе 3. Если в качестве алгоритма $A'$
использовать алгоритм Сердюкова \cite{Serd} с оценкой
$L=3/4$, то получаем $\frac {2L}{2+L} = \frac 6{11}$.
Наконец, если в качесве $A'$ использовать алгоритм из
\cite{DMPR} с рекордной на сегодня оценкой точности $L=4/5$,
то получаем $\frac {2L}{2+L} = 4/7$. Отметим также, что
если $A'$ --- это точный алгоритм решения задачи TSP-max,
то есть $L=1$, то $\frac {2L}{2+L} = 2/3$, что является
принципиальной верхней границей для оценки точности алгоритма
$A_{>1/2}$.

\bigskip
Авторы благодарны анонимному рецензенту за внимательное
изучение статьи и сделанные им ценные замечания!

\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).

\bibitem{ABG_3_4}
A.A. Ageev, A.E. Baburin, E.Kh. Gimadi, {\it A polynomial algorithm
with approximation ratio 3/4 for finding two edge-disjoint
Hamiltonian cycles of maximum  weight},  Discret. Anal. Issled.
Oper., Ser.~1, {\bf 12}:12 (2006), 11--20.
%\textbf{Агеев~А.~А., Бабурин~А.~Е., Гимади~Э.~Х.} Полиномиальный
%алгоритм с оценкой $3/4$ для нахождения двух реберно непересекающихся
%гамильтоновых циклов максимального суммарного веса~// Дискрет. анализ
%и исслед. операций. Сер.~1. 2006. Т.~13, \No~2. С.~11--20.

\bibitem{AP_09}
A.A. Ageev, A.V. Pyatkin, {\it An approximate algoritm for the metric
2-PSP with ratio 2},  Discret. Anal. Issled. Oper., {\bf 16}:4
(2009), 3--20.
%\textbf{Агеев~А.~А., Пяткин~А.~В.} Приближённый алгоритм решения
%метрической задачи о двух коммивояжёрах с оценкой точности 2~//
%Дискрет. анализ и исслед. операций. 2009. Т.~16, \No~4. С.~3--20.

\bibitem {BG_10}
A.E. Baburin, E.Kh. Gimadi, {\it On asymptotic exactness of the
effective algorithm for the maximum $m$-PSP in a multidimensional
Euclidean space}, Trudy Inst. Matem. Mechan. URO RAN, {\bf 16}:3
(2010), 12--24.
%\textbf{Бабурин~А.~Е., Гимади~Э.~Х.} Об асимптотической точности
%эффективного алгоритма решения задачи $m$-PSP на максимум в
%многомерном eвклидовом пространстве~// Тр/ ин-та математики и
%механики УРО РАН. 2010. Т.~16, \No~3. С.~12--24.

\bibitem{De_Kort}
J.B.J.M. De Kort, {\it Lower bounds for symmetric $K$-PSP},
Optimization, {\bf 22}:1 (1991), 113--122.

\bibitem{De_Kort1}
J.B.J.M. De Kort, {\it Upper bounds for the symmetric 2-PSP},
Optimization, {\bf 23}:4 (1992), 357--367.

\bibitem{De_Kort2}
J.B.J.M. De Kort, {\it A branch and bound algorithm for symmetric
2-PSP}, EJOR, {\bf 70} (1993), 229--243.


\bibitem{Diestel}
R. Diestel, {\it Graph Theory}, Springer-Verlag, New York, 2000.

\bibitem{DMPR}
S. Dudycz, J. Marcinkowski, K. Paluch, B. A. Rybicki, {\it
$4/5$-appro\-xi\-ma\-tion algorithm for the maximum Traveling
Salesman Problem}, from book Integer Programming and Combinatorial
Optimization: Proc. 19th International Conference, IPCO 2017.
(Waterloo, ON, Canada, June 26--28, 2017). Lect. Notes Comput. Sci.,
{\bf 10328} (2017), Springer, 173--185.

\bibitem{Gabow}
H.N. Gabow, {\it An efficient reduction technique for
degree-restricted subgraph and bidirected network flow problems},
Proc. 15th Annu. ACM Symp. Theory of Comput. (Boston, April 25-–27,
1983), New York: ACM, 1983, 448–-456.

\bibitem {GGG}
E.Kh. Gimadi, Yu.V. Glazkov, A.N. Glebov, {\it Approximation
algorithms for solving 2-Peripatetic Salesman Problem on a complete
graph with edge weights 1 and 2}, Discret. Anal. Issled. Oper.,
{\bf 14}:2 (2007), 41--61.
%\textbf{Гимади~Э.~Х., Глазков~Ю.~В., Глебов~А.~Н.} Приближенные
%алгоритмы решения задачи о двух коммивояжерах в полном графе с
%весами ребер 1 и 2~// Дискрет. анализ и исслед. операций. Сер.~2.
%2007. Т.~14, \No~2. С.~41--61.

\bibitem{GG_16}
A.N. Glebov, A.V. Gordeeva {\it An algorithm with approximation
ratio $5/6$ for the metric maximum $m$-PSP}, In Kochetov~Yu. et al
(eds.) DOOR-2016, Lect. Notes Comput. Sci., {\bf 9869}, Springer,
Heidelberg, 2016, 159--170.

\bibitem{GZ_7_5}
A.N. Glebov, A.V. Gordeeva, D.Zh. Zambalaeva,
{\it A 7/5-approximation algorithm for the minimum 2-Peripatetic
Salesman Problem with different weight functions}, Sib. Elektron.
Mat. Izv., {\bf 8} (2011), 296--309.
%\textbf{Глебов~А.~Н., Гордеева~А.~В., Замбалаева~Д.~Ж.} Алгоритм с
%оценкой $7/5$ для задачи о двух коммивояжерах на минимум с
%различными весовыми функциями~// Сибирские электронные
%математические известия. 2011. Т.~8. С.~296--309.

\bibitem{GT}
A.N. Glebov, S.G. Toktokhoeva, {\it A Polynomial algorithm with
asymptotic ratio 2/3 for the asymmetric maximization version of
the m-PSP}, J. Appl. Industrial Math., {\bf 14}:3 (2020), 456--469.

\bibitem{GZ_7_9}
A.N. Glebov, D.Zh. Zambalaeva, {\it A polynomial algorithm with
approximation ratio 7/9 for the maximum 2-Peripatetic Salesman
Problem}, Discret. Anal. Issled. Oper., {\bf 18}:4 (2011), 17--48.
%\textbf{Глебов~А.~Н., Замбалаева~Д.~Ж.} Полиномиальный алгоритм с
%оценкой точности $7/9$ для задачи о двух коммивояжёрах на максимум
%~// Дискрет. анализ и исслед. операций. 2011. Т.~18, \No~4.
%С.~17–-48.

\bibitem{GZ_4_3}
A.N. Glebov, D.Zh. Zambalaeva, {\it An approximation algorithm for
solving the minimum 2-Peripatetic Salesman Problem with different
weight functions}, Discret. Anal. Issled. Oper., {\bf 18}:5 (2011),
11--37.
%\textbf{Глебов~А.~Н., Замбалаева~Д.~Ж.} Приближённый алгоритм
%решения задачи о двух коммивояжёрах на минимум с различными весовыми
%функциями~// Дискрет. анализ и исслед. операций. 2011. Т.~18. \No~5,
%С.~11--37.

\bibitem{GZS}
A.N. Glebov, D.Zh. Zambalaeva, A.A. Skretneva, {\it A
$2/3$-approximation algorithm for the maximization assymetric
2-Peripatetic Salesman Problem}, Discret. Anal. Issled. Oper.,
{\bf 21}:6 (2014), 11--20.

\bibitem{Gord}
A.V. Gordeeva, {\it Polynomial algorithms with guaranteed
approximation ratios for the metric maximum 2-PSP}, Graduation thesis
of a specialist, Novosibirsk State University, 2010.
%\textbf{Гордеева~А.~В.} Полиномиальные алгоритмы с гарантированными
%оценками точности для метрической задачи о двух коммивояжёрах на
%максимум~// Выпускная дипломная работа специалиста. Новосибирск,
%НГУ, 2010.

\bibitem{Serd}
A.I. Serdyukov, {\it An algorithm with an estimate for the Traveling
Salesman Problem of the maximum}, Upravlyaemye Sistemy, {\bf 25} (1984),
80--86.

\end{thebibliography}

\end{document}
