\documentclass[twoside,11pt,a4paper]{article}
    \usepackage{daiostyle}
%%%%%%%%%%%%%%%%%% ������������ ���� ��� ���������� ������� ������ %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% ��� �������� pdf ����� �������  ���� dvi ���� ��������� � ������ ps, � ����� ps � pdf
%%% ��� ������ �� ������, ���������, �������� � ����������� ������������ ����� ������� \refsect ������ \ref

\def\families{�.~�.~������$^{1,2}$, �.~�.~����������$^2$}%�.\,�.\,������� �������  � �������� �� ���� ������.
\def\familieswithout{�.~�.~������, �.~�.~����������}%�.\,�.\,������� �������  ��� ������� ���� ������.
\def\efamilies{A.~N.~Glebov$^{1,2}$, S.~G.~Toktokhoeva$^2$}%�.\,�.\,�������  ������� c �������� ���� �� ������ �� ����������.
\def\fullnames{\sl ������~�������~����������\\����������\,������\,������������}%�������, ����� � �������� �������
\def\efullnames{{\sl Alexey~N.~Glebov\\Surena~G.~Toktokhoeva}}%�������, ����� � �������� ������� �� ����������
\def\metka{glebov}%����� ������ �������� ������.
\def\UDC{519.8}%����� ���
\def\nazvaniestati{\uppercase{�������������� �������� � ��������������� ������� �������� 2/3
��� �������������� ������ �� $m$ ���������\"e��� �� ��������}}%�������� ������
\def\enazvaniestati{\uppercase{A polynomial approximation algorithm with the asymptotic
ratio $2/3$ for the asymmetric maximization version of the $m$-PSP}}%�������� ������ �� ����������
\def\ssylka{\ffootnote{}{������������ ��������� ��� ���������� ���������
����������� ����� ��������������� ������������ (������� 18-01-00353
� 18-01-00747)}}
%\No~12--01--00093�,
%     10--07--00195�,
%      12--01--33028���\_�\_���)}}%������ �� ������� � ��������� �������. ���� ������ ��������� ��� ��������� �� ��������, ��  \ffoonote{}{...} ���������.
\def\shortname{�������� � ��������������� ������� 2/3 ��� $m$-APSP-max}%������� �������� ������ (����������� � ���� ������ �����������)
\def\annotation{� 2005~�. �������� � ��. %������������, ���������� � ��������
��� ���������� �������������� �������� � ��������������� ������� �������� 2/3 ���
��������������� ������ ������ ����������� �� ��������. � 2014~�. ������, ����������
� ��������� �������� �������� � ����� �� ������� �������� � ���������� ������� ���������
��������� ��� ��������������� ������ ������ � ���� ������������� �� ��������, ��� ���������
����� ��� ������ ���������������� ������������� ����� ������������� ���������� ����
� ������ ���������� $n$-��������� ��������������� �����. ����� ��������� ������ ��������
���������� ������������ ��������� ��� ����� ����� ������ �� $m$ ������������ �� ��������
� ��������������  ������ � ����������� ��� ����� ��������� ������ ��������, �������������� 
����������� � 2/3 � ������ $m$, � ������ �������o� ��������� $O(mn^3)$.}
\def\enannotation{In 2005, Kaplan et.al %Lewenstein, Shafrir, and Sviridenko
presented a polynomial-time algorithm with guaranteed approximation ratio 2/3 for the
maximization version of the asymmetric TSP. In 2014, Glebov, Skretneva, and Zambalaeva
constucted a similar algorithm with approximation ratio 2/3 and cubic running-time for the
maximization version of the assymetric 2-PSP problem (2-APSP-max), where the task is to find
two edge-disjoint Hamiltonian circuits of maximum total weight in a complete directed
weighted graph. In this paper we present a more general result by constructing an
approximation algorithm with the asymptotic ratio $2/3$ and with running-time $O(mn^3)$
for the $m$-APSP-max problem, where the goal is to find $m$ edge-disjoint Hamiltonian
circuits of maximum total weight in a complete directed weighted graph of order $n$.}%��������� ������ �� ����������
\def\addressesavtorov{{\rm\small$^1$ �������� ����������  ��. �.\,�.\,�������� �� ���,\\ ��. ����.
�������, 4,  630090 �����������, ������,\\ $^2$ ������������� ���.
�����������,\\ ��. ��������,~2,
630090 �����������, ������\\[1mm]}}
% ������ ������� ��� ���������, ���., �����. ���� ���� �������� � �� ��������� ������ ��������,
%�� ����������� ����� � �� ������� � ���������������� ��������
\def\eaddressesavtorov{{\rm\small$^1$Sobolev Institute of Mathematics,\\
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia\\
$^2$ Novosibirsk State University,\\ 2 Pirogov St.,
630090 Novosibirsk, Russia\\[1mm]}}% ������ ������� ��� ���������. ���� ���� �������� � �� ��������� ������ ��������,
%�� ����������� ����� � �� ������� � ���������������� �������� �� ����������
\def\familiesforcopyright{������~�.~�., ����������~�.~�.}%������� ������~�.~�.. ���� ���� ��������, �� �� ��� ����������� ����� �������
%� ��� �� ������� (��� ���������)
\def\kluchwords{����������� ����, ������ �����������, ������ ����������
������������, ����������� ��������, ��������������� ������ ��������.}%�������� �����
\def\ekluchwords{Hamiltonian cycle, Ttraveling Salesman Problem, $m$-Peripatetic
Salesman Problem, approximation algorithm, guaranteed approximation ratio.}%�������� ����� �� ����������
\def\email{angle@math.nsc.ru, s.toktokhoeva@ya.ru}%E-mail ������ �������

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\normalsize
\setcounter{page}{3}%
\beginpaper

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% ������� ������ ������ ��� ��������, ������� � ��������� %%%%%%%%%%%%%%
%%%%%%% ���� ���
\input Asymp_2_3_for_m-APSP-max.tex
%%%%%%%% ���� ����� ������ ��������������� %%%%%%%%%%%%%%%%%
\konezpaper

\end{document}
