Abstract: We consider polynomial time approximation for the minimum cost cycle cover problem of an
edge-weighted digraph, where feasible covers are restricted to have at most kdisjoint cycles. In the
literature this problem is referred to as Min-k-SCCP. The problem is closely related to classic Traveling
Salesman Problem (TSP) and Vehicle Routing Problem (VRP) and has many important applications in
algorithms design and operations research. Unlike its unconstrained variant, the Min-k-SCCP is strongly
NP-hard even on undirected graphs and remains intractable in very specific settings. For any metric, the
problem can be approximated in polynomial time within ratio 2, while in fixed-dimensional Euclidean
spaces it admits Polynomial Time Approximation Schemes (PTAS). In the same time, approximation
of the more general asymmetric Min-k-SCCP still remains weakly studied. In this paper, we propose
the first fixed-ratio approximation algorithm for this problem, which extends the recent breakthrough
Svensson-Tarnawski-V´egh and Traub-Vygen results for the Asymmetric Traveling Salesman Problem.
Key-Words: approximation algorithms, fixed ratio, asymmetric traveling salesman problem, cycle cover
problem
Received: March 4, 2024. Revised: September 8, 2024. Accepted: October 6, 2024. Published: November 5, 2024.
1 Introduction
The Cycle Cover Problem (CCP) is a well-known
combinatorial optimization problem having im-
portant applications in operations research and
algorithms design for other combinatorial prob-
lems, e.g. the Traveling Salesman Problem (TSP)
[2, 5], Vehicle Routing Problem (VRP) [11], sev-
eral versions of the Stacker Crane Problem (SCP)
[4, 8], etc.
Most of the studied CCP settings can be con-
sidered as extensions of the classic Linear Sum
Assignment Problem (LSAP) formulated on sub-
sets of the symmetric group Sn. For each such
a setting, the objective is a permutation cost co-
inciding with total weight of the corresponding
routes in a given graph, while a set of feasible per-
mutations is constrained in terms of the proper-
ties of their cycle decomposition including length
or amount of the cycles. For instance, the authors
of [3] proposed approximation algorithms for min-
imum cost graph covering problems by cycles of
length at least k. Later (see, e.g. [17] ) these
results were extended to the cheapest covers by
cycles whose lengths belong to a given set L⊂N.
In this paper, we are focused on polynomial
time approximation of the Minimum-weight k-
Size Cycle Cover Problem (Min-k-SCCP), where
it is required to construct a minimum cost cover
of a given (di)graph by at most kdisjoint cy-
cles [7, 13]. Interest to this topic is confirmed by
an intermediate complexity status of this prob-
lem between the strongly NP-hard TSP (which is
Min-k-SCCP for k= 1) and LSAP (for k=n)
that can be solved to optimality in polynomial
time.
1.1 Related work
As shown in [14, 15], for any fixed k>1, the
symmetric version of the Min-k-SCCP formu-
lated on undirected graphs inherits complexity
and main approximation properties of the clas-
sic TSP. Thus, the problem is strongly NP-hard
in general case and remains intractable even on
the Euclidean plane. The metric Min-k-SCCP is
APX-complete, while its Euclidean settings for-
mulated in Rdadmit a Polynomial Time Approx-
imation Schemes (PTAS) for an arbitrary fixed
Fixed-Ratio Approximation Algorithm for the Minimum
Cost Cover of a Digraph by Bounded Number of Cycles
DANIIL KHACHAI1, KATHERINE NEZNAKHINA2, KSENIA RIZHENKO2
MICHAEL KHACHAY2
1Centre of Excelence Supply Chain
Kedge Business School
680 cours Liberation 33405 Talence
FRANCE
2Math. Programming Lab
Krasovsky Institute of Mathematics and Mechanics
16 S. Kovalewska str. 620108 Ekaterinburg
RUSSIA
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2024.23.21
Daniil Khachai, Katherine Neznakhina,
Ksenia Rizhenko, Michael Khachay
E-ISSN: 2224-2872
218
Volume 23, 2024
dimension d. In addition, we should note asymp-
totically exact algorithms designed in [7] for the
Min-k-SCCP settings on random graphs and for
the Euclidean Max-k-SCCP.
On the other hand, polynomial time approx-
imation of the asymmetric Min-k-SCCP (as for
many other related combinatorial problems) re-
main weakly studied for a long time. For in-
stance, while constant-ratio approximation al-
gorithms for the metric TSP, metric Capaci-
tated Vehicle Routing Problem (CVRP) and their
numerous modifications have been known since
the late 1970s, thanks to the seminal results of
N. Christofides [6], A. Serdyukov [20], L. Wolsey
[23], and M. Haimovich and A. Rinnooy Kan [10],
until 2018 the Asymmetric Traveling Salesman
Problem (ATSP) could only be approximated
within the factor O(log n/ log log n) [1].
Recently, O. Svensson, J. Tarnawski, and
L. V´egh [21] and V. Traub and J. Vygen [22] in-
troduced a breakthrough approach to polynomial
time approximation of the ATSP with triangle
inequality, which led to the first fixed-ratio algo-
rithms for that problem. For the sake of conve-
nience, in the sequel we refer to this approach and
the state-of-the-art (22 + ε)-approximation algo-
rithm proposed in [22] as S(TV)2-framework and
algorithm, respectively.
Relying on this algorithm as a building block,
the first proofs of polynomial time approxima-
tion within fixed factors for several related asym-
metric problems including Steiner Cycle Problem
(SCP), Rural Postman Problem (RPP), CVRP
with unsplittable demands [16] and Prize Collect-
ing ATSP [18] were obtained.
At the same time, for some routing problems,
e.g. for Min-k-SCCP, fixed-ratio approximation
algorithms still cannot be designed in a similar
way, just on the basis of cost-preserving reduction
to single or multiple auxiliary ATSP instances.
To this end, one can assume that some of these
problems can be approximated within fixed ratios
by more deep extension of S(TV)2-framework.
1.2 Contribution
In this paper
(i) we extend the S(TV)2-framework to the class
of routing problems including Min-k-SCCP
for k>1;
(ii) for an arbitrary ε > 0, we propose the first
polynomial time (24 + ε)-approximation for
the Min-k-SCCP.
The rest of the paper is structured as follows.
In Section 2, we recall a mathematical formula-
tion of Min-k-SCCP. In the following sections, we
show that the initial task of construction of a
fixed-ratio approximation algorithm for the Min-
k-SCCP can be successively reduced to the sim-
ilar tasks for more structured instance of this
problem, i.e. Min-k-SCCPS(in Section 3), and
strongly laminar instances (in Section 4). We
present our main results: (24 + ε)-approximation
algorithm for the Min-k-SCCPSand the proof of
its performance guarantee in Section 5. Finally,
in Section 6 we summarize our paper.
2 Problem statement
Suppose, we are given by a strongly connected di-
graph G= (V, E) and weighting function c:E→
R+that specifies transportation cost ce=c(e) =
c(v, w) for a transition along each arc e= (v, w)∈
Eof the graph G. Hereinafter, we assume that
the triangle inequality
c(v, w)6c(v, u) + c(u, w) (1)
holds for any arcs (v, u), (u, w), and (v, w). To
any multi-set of arcs F, we assign the incidence
vector x=χF,x:E→Z+and cost c(F) =
Pe∈Ecexe.
Definition 1. An instance of the Min-k-SCCP is
defined as follows. For an ordered pair (G, c), it
is required to compute a spanning Eulerian sub-
multigraph GF= (V, F )of the digraph G, such
that
(i) GFhas no isolated nodes
(ii) GFhas at most kconnected components
(iii) Fhas the minimum cost c(F).
Although the given statement slightly gener-
alizes the known formulation of the Min-k-SCCP
studied in previous papers [7, 15], these formula-
tions coincide to each other for complete graphs.
Furthermore, the classic ATSP is Min-k-SCCP
for k= 1.
3 Restricted Min-k-SCCP
In this section, we reduce approximation of the
Min-k-SCCP to the same task for the restricted
version of this problem, which we call Min-k-
SCCPS.
Definition 2. An instance of the Min-k-SCCPS
is given by a triple (G, c, S), where S⊂V,
|S|=k. It is required to find a spanning Eu-
lerian submultigraph GF, which along with con-
ditions (i)–(iii) satisfies an additional constraint:
V(D)∩S6=∅for any connected component Dof
GF.
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2024.23.21
Daniil Khachai, Katherine Neznakhina,
Ksenia Rizhenko, Michael Khachay
E-ISSN: 2224-2872
219
Volume 23, 2024
We use standard notation δ+(U) =
{(v, w): v∈U, w ∈V\U},δ−(U) = δ+(V\U),
and δ(U) = δ−(U)∪δ+(U) for the cuts specified
by an arbitrary non-empty subset of nodes
U⊂V. In addition, we use the abbreviations
δ(v) = δ({v}) and x(E0) = Pe∈E0xefor any
v∈Vand subset of arcs E0⊂E. By OPT and
OPTSwe denote the costs of optimum solutions
of the initial Min-k-SCCP instance (G, c) and the
corresponding auxiliary Min-k-SCCPSinstances
(G, c, S), respectively.
Lemma 1. For arbitrary k>1and α > 0, ex-
istence of an α-approximation polynomial algo-
rithm for the Min-k-SCCPSimplies polynomial
time approximation for the Min-k-SCCP within
the same ratio.
Proof. Let (G, c) be a Min-k-SCCP instance to be
solved and ASbe the α-approximation algorithm
for the Min-k-SCCPS. Since Gis strongly con-
nected, the instance (G, c) and all the auxiliary
instances (G, c, S) for S⊂V,|S|=kare feasi-
ble and can be solved to optimality. By applying
algorithm ASto any instance (G, c, S) we assign
the spanning Eulerian subgraph GS= (V, FS),
such that, for each connected component Dof the
graph GS,V(D)∩S6=∅and OPTS6c(FS)6
αOPTS.
Further, let H∗= (V, F ∗) be an optimal solu-
tion of the initial instance (G, c) and S∗⊂Vbe
an arbitrary k-element subset, which has a non-
empty intersection with any connected compo-
nent of the graph H∗. Then, for the subgraph
(V, F ) = arg min{c(FS) : S⊂V, |S|=k}, we
have
OPT 6c(F)6c(FS∗)6α·OPTS∗
6α·c(F∗) = α·OPT .
Thus, the Min-k-SCCP has an α-approximation
polynomial time algorithm, since
{S⊂V:|S|=
k}
=O(nk). Lemma is proved.
4 Strongly laminar instances
We proceed with approximation algorithms for
the Min-k-SCCPSby assignment to this problem
the following MILP-model
min X
e∈E
cexe(2)
s.t. x(δ−(v)) −x(δ+(v)) = 0 (v∈V),(3)
x(δ(U)) >2 (U∈ V),(4)
xe∈Z+(e∈E),(5)
where V={U:∅6=U⊂V\S} ∪ {{u}:u∈S}.
Here, equations (3) ensure that any feasible sub-
multigraph will be Eulerian while (4) provide an
absence of the isolated nodes and upper bound for
the number of its connected components. In the
sequel, we consider LP-relaxation Pof problem
(2)–(5) and its dual D:
max X
U∈V
2yU
s.t.
aw−av+X
U∈V :e∈δ(U)
yU6c(e) (e= (v, w)∈E)
yU>0 (U∈ V).
Under our assumptions, both problems are solv-
able and have the same optimal value P∗=D∗.
In this section, we show that approximation
of the Min-k-SCCPScan be reduced to the case
of structured instances of this problem called
strongly laminar. Recall that a family of sub-
sets Lof the set Vis called laminar, if for any
L1, L2∈ L,L1∩L26=∅implies either L1⊆L2
or L2⊆L1.
Definition 3. A tuple I= (G, L, k, S, x, y)is a
strongly laminar Min-k-SCCPSinstance, if
-G= (V, E)is a strongly connected digraph
and |V|> k;
-Sis a subset of Vof size k;
-Lis a laminar family of subsets of V\S,
such that for any L∈ L, the induced subgraph
G[L]is strongly connected;
-x:E→R+is a feasible solution for (3)–(4),
s.t. x(δ(L)) = 2 for an arbitrary L∈ L;
-y:L → R+.
Each Iinduces the structured instance
(G, ¯c, S) of the Min-k-SCCPSwith special
weighting function
¯ce= ¯c(e) = X
L∈L:e∈δ(L)
yL(e∈E) (6)
Define y0:V → R+as follows:
y0
U=yU,if U∈ L,
0,otherwise.
By construction, xand (0, y0) are optimal solu-
tions of the corresponding linear programs Pand
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2024.23.21
Daniil Khachai, Katherine Neznakhina,
Ksenia Rizhenko, Michael Khachay
E-ISSN: 2224-2872
220
Volume 23, 2024
D, for c≡¯c. In the sequel, we call these problems
Pind and Dind) and use the following notation
LP(I) = P∗
ind =X
e∈E
¯cexe=X
L∈L
2yL=D∗
ind.(7)
The concept of strongly laminar Min-k-
SCCPSinstance is a natural extension of the
known concept of strongly laminar ATSP in-
stance. In [22], those instances were considered
for k= 1. In our case, we use a more simple no-
tation I= (G, L, x, y). Furthermore, as in [21],
in the case where Lconsists only singletons {v},
we refer to Ias singleton instance of the Min-k-
SCCPS.
Lemma 2. Suppose, for some α>1, there ex-
ists a polynomial time algorithm that that, for any
strongly laminar instance I= (G, L, l, S, x, y),
l6k, computes a feasible solution of cost at
most α·LP(I). Then, there exists a polynomial
time algorithm that, for an arbitrary instance of
Min-k-SCCPS, finds a feasible solution of cost
c(FS)6α· P∗.
Proof. Consider an arbitrary Min-k-SCCPSin-
stance (G, c, S). Let x∗be an optimal solution of
the LP-relaxation P. Although Phas an expo-
nential number of constraints (4), x∗can be found
in polynomial time, e.g. by the ellipsoid method
augmented with polynomial time separation ora-
cle [9]. In addition, without loss of generality, we
can assume that
U∈ V :x∗(δ(U)) = 2
=poly(n).(8)
By construction, the graph G0= (V, E0), where
E0={e∈E:x∗>0}has at most kstrongly
connected components W1, . . . , Wpfor p6k. Be-
sides that, there exists a partition S1∪. . . ∪Spof
the set S, such that Si⊂Wifor each i= 1, p. By
x0[i] we denote the restriction of x∗on E0(Wi).
Let us verify that x0[i] is an optimal solution
of the LP-relaxation Piof the model (2)–(5) for
the instance (Wi, ki, Si), where ki=|Si|. Indeed,
the equations
x0[i](δ−(v)) −x0[i](δ+(v)) = 0 (v∈V(Wi))
x0[i](δ(U)) >2 (U∈ Vi),
for Vi=U:∅6=U⊂V(Wi)\Si∪{u}:c∈
Si, follows straightforwardly from the choice of
x0[i]. Next, optimality of x0[i] in problem Pifol-
lows from the evident decomposition
P∗=X
e∈E
cex∗
e=
p
X
i=1 X
e∈E(Wi)
ce(x0[i])e(9)
and the optimality of x∗in problem P.
For each i= 1, p find an optimal solution
(a∗[i], y∗[i]) of the dual Di. Due to (8), these
computations can also be carried out in polyno-
mial time. Applying Karzanov’s algorithm [12]
and following the argument of [22, Lemma 3], to
any solution (a∗[i], y∗[i]) we assign an optimal so-
lution (a0[i], y0[i]) of Di, such that supp(y0[i]) =
Li={U∈ Vi: (y0[i])U>0}is a laminar fam-
ily and, for any L∈ Li, the subgraph Wi[L] is
strongly connected.
By y00[i] denote the restriction of y0[i] onto
Liand introduce the strongly laminar instance
Ii= (Wi,Li, ki, Si, x0[i], y00[i]). By construction,
the problems Piand (Pi)ind have the same set
of feasible solutions. Furthermore, for the corre-
sponding weighting functions ceand ¯ce, we have
ce= ¯ce+ (a0[i])w−(a0[i])v, which follows from (6)
and the complementarity conditions. As a con-
sequence, for an arbitrary feasible solution χof
both problems, we have
X
e∈E0(Wi)
ceχe=X
e=(v,w)∈E0(Wi)
(¯ce+(a0
w[i])−(a0
v[i]))χe
=X
e∈E0(Wi)
¯ceχe+X
u∈V(Wi)
(χ(δ−(u))−χ(δ+(u)))(a0[i])u
=X
e∈E0(Wi)
¯ceχe.(10)
Finally, by the hypothesis of Lemma 2, for
each instance Iiin polynomial time we can find
a solution (Wi, Fi), such that ¯c(Fi)6αLP(()Ii),
which implies c(Fi)6αP∗
idue to (10). There-
fore, the subgraph (V, F ), where F1∪. . . ∪Fp,
is a desired approximate solution for the initial
Min-k-SCCPSinstance (G, c, S) of cost
c(F) =
p
X
i=1
c(Fi)6α
p
X
i=1
P∗
i=α· P∗,
where the last equality follows from (9). Lemma
is proved.
5 Approximation of a strongly
laminar instance
In this section, we propose an approximation al-
gorithm for strongly laminar instances of the Min-
k-SCCPS. Consider an arbitrary strongly lami-
nar instance I= (G, L, k, S, x, y) with induced
weighting function c.
5.1 Preliminaries
We start with some necessary additional nota-
tion and preliminary technical results. Let W∈
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2024.23.21
Daniil Khachai, Katherine Neznakhina,
Ksenia Rizhenko, Michael Khachay
E-ISSN: 2224-2872
221
Volume 23, 2024
L∪{V}be the minimal subset that contains
nodes uand v. The u-v-path Pu,v in the strongly
connected subgraph G[W] (of the graph G) and
visiting each L∈ L at most once is called a nice
path. As shown in [22], for arbitrary uand vthe
nice path Pu,v can be found in polynomial time
and its cost is defined by the formula
c(E(Pu,v)) = X
L∈LW:L∩V(Pu,v )6=∅
2yL
−X
L∈LW:u∈L
yL−X
L∈LW:v∈L
yL,(11)
where LW={L∈ L:L⊂W}. It is useful to
assign to each subset Wthe value
DW= max{DW(u, v): u, v ∈W},(12)
where
DW(u, v) = c(E(Pu,v)) + X
L∈LW:u∈L
yL
+X
L∈LW:v∈L
yL.(13)
We slightly extend the concept of a backbone in-
troduced in [21].
Definition 4. A Eulerian submultigraph with-
out isolated nodes Bof the graph Gis called S-
backbone, if
-V(B)∩L6=∅for any L∈ L>2={L∈
L:|L|>2}
-S⊂V(B)
-V(D)∩S6=∅holds for an arbitrary con-
nected component Dof B.
Definition 5. An ordered pair (I, B), where I
is a strongly laminar Min-k-SCCPSinstance and
Bis an S-backbone, is called a vertebrate pair.
The fixed-ratio approximation algorithm pro-
posed in [22] for the ATSP relies on an efficient
building block called (κ, η)-algorithm for verte-
brate pairs. For given parameters κ, η >0 and
arbitrary vertebrate pair (I, B), this algorithm
computes in polynomial time a set of arcs F0,
such that (V, E(B)∪F0) is a spanning Eulerian
connected submultigraph of Gand
c(F0)6κLP(I) + η·X
v∈V\V(B):{v}∈L
2y{v}.(14)
As follows from [22], for any ε > 0 and (I, B),
where Ias a strongly laminar ATSP instance and
Bis an arbitrary connected backbone, there ex-
ists (2,14 + ε)-algorithm for vertebrate pairs.
We extended (κ, η)-algorithm to the case of
vertebrate pairs, where Iis a strongly laminar
Min-k-SCCPSinstance and Bis an S-backbone.
Lemma 3. For any k > 1,ε > 0, there ex-
ists a polynomial time algorithm, which extends
the S-backbone Bof an arbitrary vertebrate pair
(I, B)to a feasible solution of the Min-k-SCCPS
instance Iby appending a multiset of arcs F0,
such that (14) is valid for κ= 2 and η= 14 + ε.
The proof of Lemma 3 can be obtained in a
similar way to the argument of [22, Theorem 35],
where existence of (κ, η)-algorithm for η= 4α+
β+1+εwas proved as a consequence of existence
of the polynomial time (α, κ, β)-algorithm for an
auxiliary Subtour Cover Problem (SCP). In turn,
(α, κ, β)-algorithm for the SCP was developed (in
[22, Theorem 16]) on top of the well-known flow
rerouting and rounding technique (see, e.g. [19])
applicable if
x(δ(U)) >2 (∅6=U⊂V\V(B)).(15)
In the ATSP, inequality (15) follows straightfor-
wardly from the problem formulation. In our
case, we ensure it by introducing S-backbones.
For the sake of brevity, we postpone the full
rather technical proof to the forthcoming paper.
5.2 Algorithm: scheme and discussion
The proposed algorithm (Algorithm A) computes
a feasible solution GF= (V, F ) of a given strongly
laminar Min-k-SCCP instance I, where GFis
a spanning submultigraph of the graph G, each
whose connected component Dintersects the set
S, i.e. V(D)∩S6=∅. As outer parameters,
Algorithm Atakes the (κ, η)-algorithm Aκ,η for
vertebrate pairs (see Def. 4 and Lemma 3) and
(3κ+η+ 2)-approximation algorithm A∗
AT SP for
the ATSP [22].
At step 1, we construct the family L¯
Scon-
sisting of high-level non-singleton elements of the
laminar family L. By construction, all of them do
not intersect the set S. Therefore, the instance
I0obtained at step 2 is a singleton instance. Fur-
ther, at step 3, the S-backbone Bcan be com-
puted from the cycle cover provided by (2,0)-light
algorithm [21, Th. 4.1] or by a sampling. At step
4, we extend Bto a solution for the contracted
graph, which is augmented with ATSP tours for
each L∈ L ¯
Sat steps 5–8. Finally, at step 9, we
combine all the parts of the resulting solution.
Lemma 4. For any k > 1and κ, η >0, ex-
istence of a polynomial time (κ, η)-algorithm for
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2024.23.21
Daniil Khachai, Katherine Neznakhina,
Ksenia Rizhenko, Michael Khachay
E-ISSN: 2224-2872
222
Volume 23, 2024
Algorithm A
Input: strongly laminar Min-k-SCCPS
instance I= (G, L, k, S, x, y)
Parameters: (κ, η)-algorithm Aκ,η for vertebrate
pairs; algorithm A∗
AT SP ;
Output: a feasible solution GF= (V, F ) of the
instance I.
1: set up a sub-family
L¯
S=L∈ L>2: (V(S)∩L=∅)
∧(∀U∈ L:L⊂U)(V(S)∩U6=∅)
2: construct a singleton Min-k-SCCPSinstance I0=
(G0,L0, k, S, x0, y0), where
a: multigraph G0= (V0, E0) is obtained by contract-
ing each L∈ L ¯
Sinto the corresponding node vL,
b: laminar family
L0=L \ L∈ L: (∃U∈ L ¯
S) (L⊆U)[
L∈L ¯
S
{vL}
c: vector x0is a restriction of xon E0and y0:L0→R+
is defined by:
y0
U=(yU,if U∈ L ∩ L0
yL+DL/2,otherwise (16)
3: construct an S-backbone B
4: apply algorithm Aκ,η to the vertebrate pair (I0, B) and
compute the Eulerian multiset of arcs F0(in the graph
G0)
5: for each L∈ L ¯
Sdo
6: obtain a traveling salesman tour FLin Lby apply-
ing A∗
AT SP to (I, L)
7: extend Flby a nice path PLin G[L] to ensure that
the resulting solution remains a Eulerian graph
8: end for
9: set F=SL∈L ¯
S(FL∪PL)˙
∪E(B)˙
∪F0
10: return (V, F ).
vertebrate pairs (Def. 5) implies the existence of
an algorithm which, for an arbitrary strongly lam-
inar Min-k-SCCPSinstance I, computes in poly-
nomial time a feasible solution (V, F )of cost
cost(F)6(3κ+η+ 4) LP(I).(17)
Proof. Since Aκ,η and A∗
AT SP are polynomial
time algorithms, all the steps of Algorithm Acan
be carried out in polynomial time as well.
To prove (17), obtain upper bounds for the
costs C(F0), c(E(B)) and c(FL) separately. By
(14) and (16), for c(F0) we have
c(F0)6κ·LP(I0) + η·X
L∈L ¯
S
2y0
{vL}
+X
v6∈V(B): {v}∈L∩L0
2y0
{v}
=κ·X
L∈L∩L0
2yL+X
L∈L ¯
S
(2yL+DL)
+η·X
v6∈V(B): {v}∈L∩L0
2y{v}+X
L∈L ¯
S
(2yL+DL)
=κ·X
L∈L∩L0
2yL+ (κ+η)·X
L∈L ¯
S
(2yL+DL)
+η·X
v6∈V(B): {v}∈L∩L0
2y{v}.
Next, for each FLdue to [22, Lemma 12],
c(FL) + c(PL)
6(2κ+ 2) LP(IL)+(κ+η)(LP(IL)−DL)
= (3κ+η+ 2) LP(IL)−(κ+η)DL,
where LP(IL) = P
U∈L:U⊂L
2yU.
Further, by [21, Th. 4.1],
c(E(B)) 62 LP(I0)
= 2 ·X
L∈L∩L0
2yL+X
L∈L ¯
S
(2yL+DL).
Finally, taking into account that DL6LP(I)
and
X
L∈L ¯
S
2yL+X
v6∈V(B): {v}∈L∩L0
2y{v}
+X
L∈L ¯
S
LP(IL)6LP(I),
we obtain
c(E(B)) + c(F0) + X
L∈L ¯
Sc(FL) + c(PL)
6(κ+2) X
L∈L∩L0
2yL+(κ+η+2) X
L∈L ¯
S
(2yL+DL)
+ηX
v6∈V(B): {v}∈L∩L0
2y{v}+X
L∈L ¯
S(3κ+η+2) LP(IL)
−(κ+η)DL6(3κ+η+ 2) LP(I)+2 X
L∈L ¯
S
DL
6(3κ+η+ 4) LP(I).
Lemma is proved.
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2024.23.21
Daniil Khachai, Katherine Neznakhina,
Ksenia Rizhenko, Michael Khachay
E-ISSN: 2224-2872
223
Volume 23, 2024
Now, we are ready to formulate our main results,
which easily follow from the proved lemmas.
Theorem 1. For an arbitrary k>1and ε >
0, there exists a polynomial time algorithm that
assigns to an arbitrary instance (G, c, S)of the
Min-k-SCCPSan approximate solution (V, FS)of
cost c(FS)6(24 + ε)· P∗, where Pis an LP-
relaxation of the MILP-model (2)–(5).
Theorem 2. For an arbitrary k>1and ε > 0,
the Min-k-SCCP can be approximated within a
ratio 24 + εby a polynomial time algorithm.
6 Conclusion
In this paper, by extending the breakthrough
results of O. Svensson, J. Tarnawski, L. V´egh,
V. Traub, and J. Vygen, we proposed the first
fixed-ratio approximation algorithm for the prob-
lem of computing a minimum cost cover of a di-
graph by at most kcycles (Min-k-SCCP). We
showed that, for any k > 1 and ε > 0, the Min-k-
SCCP can be approximated in polynomial time
within the ratio 24 + ε. The believe that the our
approach can be extended to more wide class of
asymmetric routing problems.
References:
[1] Asadpour, A., Goemans, M.X., Mkadry,
A., Gharan, S.O., Saberi, A.: An
O(log n/loglog n)-approximation al-
gorithm for the asymmetric travel-
ing salesman problem. Operations
Research 65(4), 1043–1061 (2017).
https://doi.org/10.1287/opre.2017.1603
[2] Bl¨aser, M., Manthey, B., Sgall, J.: An
improved approximation algorithm for
the asymmetric TSP with strength-
ened triangle inequality. Journal of
Discrete Algorithms 4, 623–632 (2006).
https://doi.org/10.1016/j.jda.2005.07.004
[3] Bl¨aser, M., Siebert, B.: Computing
cycle covers without short cycles. In:
Algorithms—ESA 2001, pp. 368–379.
Springer (2001)
[4] Bordenave, C., Gendreau, M., Laporte,
G.: Heuristics for the mixed swap-
ping problem. Computers & Opera-
tions Research 37(1), 108–114 (2010).
https://doi.org/10.1016/j.cor.2009.03.032
[5] Chandran, S.L., Ram, S.L.: On the
relationship between ATSP and the
cycle cover problem. Theoretical Com-
puter Science 370(1), 218–228 (2006).
https://doi.org/10.1016/j.tcs.2006.10.026
[6] Christofides, N.: Worst-case analysis of a
new heuristic for the Traveling Salesman
Problem. In: Symposium on New Directions
and Recent Results in Algorithms and Com-
plexity. p. 441 (1975)
[7] Gimadi, E.K., Rykov, I.: Asymptotically
optimal approach to the approximate
solution of several problems of covering
a graph by nonadjacent cycles. Proc.
Steklov Inst. of Math. 295, 57 – 67 (2016).
https://doi.org/10.1134/S0081543816090078
[8] Graf, B.: Preemptive Stacker Crane
Problem: extending tree-based prop-
erties and construction heuristics.
European Journal of Operational
Research 292(2), 532–547 (2021).
https://doi.org/10.1016/j.ejor.2020.10.051
[9] Gr¨otschel, M., Lov´asz, L., Schrijver,
A.: The ellipsoid method and its con-
sequences in combinatorial optimization.
Combinatorica 1(2), 169–197 (1981).
https://doi.org/10.1007/BF02579273
[10] Haimovich, M., Rinnooy Kan, A.H.G.:
Bounds and heuristics for capacitated
routing problems. Mathematics of Oper-
ations Research 10(4), 527–542 (1985).
https://doi.org/10.1287/moor.10.4.527
[11] Hassin, R., Rubinstein, S.: On the
complexity of the k-customer vehi-
cle routing problem. Operations Re-
search Letters 33, 71–76 (2005).
https://doi.org/10.1016/j.orl.2004.04.003
[12] Karzanov, A.V.: How to tidy up a symmetric
set-system by use of uncrossing operations.
Theoretical Computer Science 157(2), 215–
225 (1996). https://doi.org/10.1016/0304-
3975(95)00160-3
[13] Khachai, M., Neznakhina, E.: Approxima-
bility of the problem about a minimum-
weight cycle cover of a graph. Doklady
Mathematics 91(2), 240–245 (2015).
https://doi.org/10.1134/S1064562415020313
[14] Khachai, M., Neznakhina, E.: A polynomial-
time approximation scheme for the eu-
clidean problem on a cycle cover of a
graph. Proceedings of the Steklov Institute
of Mathematics 289(1), 111–125 (2015).
https://doi.org/10.1134/S0081543815050107
[15] Khachay, M., Neznakhina, K.: Ap-
proximability of the Minimum-Weight k-
Size Cycle Cover Problem. Journal of
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2024.23.21
Daniil Khachai, Katherine Neznakhina,
Ksenia Rizhenko, Michael Khachay
E-ISSN: 2224-2872
224
Volume 23, 2024
Global Optimization 66(1), 65–82 (2016).
https://doi.org/10.1007/s10898-015-0391-3
[16] Khachay, M., Neznakhina, E., Ryzhenko, K.:
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(1), S140–S155 (2022).
https://doi.org/10.1134/S0081543822060128
[17] Manthey, B.: Minimum-weight cycle cov-
ers and their approximability. Discrete Ap-
plied Mathematics 157, 1470–1480 (2009).
https://doi.org/10.1016/j.dam.2008.10.005
[18] Rizhenko, K., Neznakhina, K., Khachay,
M.: Fixed ratio polynomial time approx-
imation algorithm for the Prize-Collecting
Asymmetric Traveling Salesman Problem.
Ural math. journal 9(1), 135–146 (2023).
https://doi.org/10.15826/umj.2023.1.012
[19] Schrijver, A.: Combinatorial Optimization -
Polyhedra and Efficiency. Springer (2003)
[20] Serdyukov, A.I.: Some extremal bypasses in
graphs (in Russian). Upravlyaemye Systemy
= Controllable Systems (76–79) (1978)
[21] Svensson, O., Tarnawski, J., V´egh, L.A.:
A constant-factor approximation algo-
rithm for the asymmetric traveling sales-
man problem. J. ACM 67(6) (2020).
https://doi.org/10.1145/3424306
[22] Traub, V., Vygen, J.: An improved ap-
proximation algorithm for the asymmetric
traveling salesman problem. SIAM Jour-
nal on Computing 51(1), 139–173 (2022).
https://doi.org/10.1137/20M1339313
[23] Wolsey, L.A.: Heuristic analysis, linear
programming and branch and bound. In:
Rayward-Smith, V.J. (ed.) Combinatorial
Optimization II, pp. 121–134. Springer
Berlin Heidelberg, Berlin, Heidelberg (1980).
https://doi.org/10.1007/BFb0120913
Contribution of individual
authors to the creation of a
scientific article (ghostwriting
policy)
Michael Khachay and Katherine Neznakina
proposed general ideas of the proposed approx-
imation framework and formulations of main
theorems.
Ksenia Rizhenko designed Algorithm A.
Daniil Khachai and Ksenia Rizhenko proved all
the lemmas.
Sources of funding for research
presented in a scientific article
or scientific article itself
Research of Katherine Neznakhina, Ksenia
Rizhenko, and Michael Khachay was sup-
ported by Russian Science Foundation, grant
no. 22-21-00672, https://rscf.ru/project/
22-21-00672/.
Conflict of Interest
The authors have no conflicts of interest to declare
that are relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2024.23.21
Daniil Khachai, Katherine Neznakhina,
Ksenia Rizhenko, Michael Khachay
E-ISSN: 2224-2872
225
Volume 23, 2024
