When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?.
We consider the probabilistic relationship between the value of a random asymmetric traveling  salesman problem $ATSP(M)$ and the value of its assignment relaxation $AP(M)$. We assume here  that the costs are given by an $n\times n$ matrix $M$ whose entries are independently and  identically distributed. We focus on the relationship between $Pr(ATSP(M)=AP(M))$ and the  probability $p_n$ that any particular entry is zero. If $np_n\rightarrow \infty$ with $n$  then we prove that $ATSP(M)=AP(M)$ with probability 1-o(1). This is shown to be best possible  in the sense that if $np(n)\rightarrow c$, $c>0$ and constant, then $Pr(ATSP(M)=AP(M))<1-\phi(c)$  for some positive function $\phi$. Finally, if $np_n\rightarrow 0$ then $Pr(ATSP(M)=AP(M))\rightarrow 0$.
Introduction
The Assignment Problem (AP) is the problem of finding a minimum-weight perfect matching
in an edge-weighted bipartite graph.An instance of the AP can be specified by an n \Theta n
represents the weight of the edge between x i and y j , where
is the set of "left vertices" in the bipartite graph, and
is the set of "right vertices."The AP can be stated in terms of the matrix M as follows: find
a permutation oe of f1; ng that minimizes
(M) be the optimal
value of the instance of the AP specified by M .
The Asymmetric Traveling-Salesman Problem (ATSP) is the problem of finding a Hamiltonian
circuit of minimum weight in an edge-weighted directed graph. An instance of the
ATSP can be specified by an n \Theta n matrix denotes the weight of
?. The ATSP can be stated in terms of the matrix M as follows: find a cyclic
permutation - of f1; ng that minimizes
here a cyclic permutation is one
whose cycle structure consists of a single cycle. Let ATSP (M) be the optimal value of the
instance of the ATSP specified by M .
It is evident from the parallelism between the above two definitions that AP (M) -
ATSP (M ). The ATSP is NP-hard, whereas the AP is solvable in time O(n 3 ). Several
authors (for a recent survey see [BaTo]) have investigated whether the AP can be used
effectively in a branch-and-bound method to solve the ATSP. The most striking evidence
of the power of this approach is given by the recent work of Miller and Pekny. Among
many other computational results, they obtained optimal solutions to random instances
with up to 500,000 cities, in which the m ij were drawn independently from the integers
in the range [0; n]. Miller and Pekny noticed that AP (M) was often equal to ATSP (M ),
and they exploited this observation by developing a special method to search for a cyclic
permutation among the optimal solutions to the AP.
Motivated by the computational experience of Miller and Pekny, we have investigated
the following question: when the m ij are drawn independently from a common distribution
(over, say, the nonnegative reals), what is the probability that AP (M)? The
answer depends on the probability that an entry is zero. We show that, if the expected
number of zeros in a row of M tends to infinity as then the probability that
tends to 1, and we give an O(n 3 )-time algorithm for finding an
optimal solution to the ATSP with high probability; on the other hand, if the underlying
distribution is uniform over the range of integers [0::bc n nc], where c n tends to infinity with
n, then the probability that AP tends to 0. Finally, we show that if the
underlying distribution is uniform over the range of integers [0::bcnc] where c is a positive
constant, then the probability that AP does not tend to 1. We conjecture
that for distributions of this type, the probability that AP tends to some
positive constant less than 1 which depends on c.
The results of this paper are closely related to some earlier results of Karp [K], Karp
and Steele [KS] and Dyer and Frieze [DF]. Here the m i;j are drawn independently from the
uniform distribution over [0,1]. Karp showed that ATSP (M)=AP
(we use the notation (whp) as shorthand for "with probability tending to 1 as n tends to
Later, Karp and Steele and then Dyer and Frieze strengthened this result in
several ways. For example the latter paper shows that the error term is o((log n) 4 =n).
2 The Theorems
Let fX n g be a sequence of random variables over the nonnegative reals. Let p
0] and let be an n \Theta n matrix whose entries are drawn
independently from the same distribution as X n . If w(n) ! 1 as
ATSP (M) (whp).
(Examination of the proof of Theorem 2 reveals that the distribution of non-zeros can
be more complicated than actually stated. Indeed one can allow the costs to be generated
as follows: start with an arbitrary real non-negative n \Theta n matrix M . Randomly permute
its rows and columns. Then for each replace M i;j with zero, with probability p n .
There is also the proviso that the probability of two identical columns should tend to zero
with n.)
Frieze [Fr] has shown that, if tends to infinity, then
(whp). Thus, we restrict attention
to the case where n). The case where X n has the uniform distribution over
the range of integers [0::N(n)] is particularly relevant to the Miller-Pekny computations. In
this case, Theorem 1 tells us that AP
be an n \Theta n matrix whose entries are drawn independently from the
uniform distribution over f0; 1; :::; bcncg where c is a positive constant. Then, the probability
that AP (M) 6= ATSP (M) does not tend to zero as n tends to infinity.
be an n \Theta n matrix whose entries are drawn independently from the
uniform distribution over f0; 1; :::; bc n ncg where c n tends to infinity with n. Then, the
probability that AP (M) 6= ATSP (M) tends to 1 as n tends to infinity.
3 Proof of Theorem 1
We begin with some conventions and definitions.When n is understood from context we
abbreviate p n by p, w(n) by w and M(n) by M ; also, "permutation" will mean "permutation
of
Let H be the weighted bipartite graph with vertex set X[Y , where
and with an edge of weight m ij between x i and y j . Let G be the
complete digraph on vertex set f1; which each edge !
cycle cover is a subgraph of G in which each of the n vertices has in-degree 1 and out-degree
1. The AP can be stated in any of the following equivalent forms:
ffl Find a perfect matching of minimum weight in H ;
ffl find a cycle cover of minimum weight in G;
ffl find a permutation oe to minimize
Let the indicator variable z ij be 1 otherwise. Then the z ij are indepen-
dent, and each z ij is equal to 1 with probability p. Emulating a useful trick due to Walkup
[Wal1] we view the z ij as being generated in the following way. Let h be defined by the
ij , for
be independent indicator variables, each of which is equal to 1 with probability h. Let
ij . Then the z ij are independent, and each is equal to 1 with probability
p. For be the bipartite graph with vertex set X [ Y , and with an edge
between x i and y j if and only if z k
1. For be the digraph with vertex
set ng and an edge from i to j if and only if z k
1. The edges of G 3 , G 4 and
respectively, will be called out-edges, in-edges and patch edges. Each type of edge will
play a special role in the construction of a Hamiltonian circuit of weight AP (M ). It will be
important that the random graphs H 1 and H 2 , and the random digraphs G 3 ; G 4 and G 5 ,
are completely independent. Also, let is the expected degree of a vertex
in H 1 or H 2 , and the expected out-degree of a vertex in G 3 , G 4 or G 5 . Clearly, s(n) - w(n),
and thus s(n) tends to infinity if w(n) does.
The construction of the desired Hamiltonian circuit proceeds in the following stages:
ffl (Identification of "troublesome vertices.") By considering the edges of H 1 [H 2 identify
a set A ae X and a set B ae Y . The cardinality of A [ B is small (whp). The set
contains the vertices of exceptionally small degree plus certain other vertices
that are likely to be incident with edges of nonzero weight in an optimal assignment.
At the same time construct a matching in H which is of minimum weight, subject to
the condition that it covers the vertices in A [ B and no other vertices.
ffl Consider the subgraph of H 1 [H 2 induced by (X n A)[ (Y n B). This bipartite graph
has a perfect matching (whp). Combining that perfect matching with the matching
constructed in the previous step, obtain an optimal assignment for H in which every
non-zero-weight edge is incident with a vertex in A [ B.
ffl The optimal assignment just constructed has the properties of a random permutation.
ffl Using the out-edges and in-edges, attempt to convert the original optimal assignment
into a permutation with no short cycles. This process succeeds (whp).
ffl Using the patch edges, patch the long cycles together into a single cycle, thus solving
the ATSP . The patching process succeeds (whp).
The overall strategy of the proof is to construct an optimal assignment while keeping
the in-edges, out-edges and patch edges (except those incident with A [ B) in reserve for
use in converting the optimal assignment to a tour. In the following sections we describe
the algorithm in greater detail and give the proofs of the main assertions.
4 Identification of the Sets A and B
Consider the directed bipartite graph D with vertex set X [Y . The edges of D are those of
directed from X to Y plus those of H 2 directed from Y to X . The expected out-degree
of a vertex in D is s(n), which we abbreviate by s. Let d(v) be the out-degree of vertex v,
let N(v) be the set of out-neighbors of v and, for any set of vertices S, let N(S) be the set
of vertices adjacent from vertices in S.
We give an iterative construction for identifying a small set A [ B of vertices that are
likely to be incident with edges of nonzero weight in an optimal assignment. Let W
s=2g. Let F 0 be a minimum weight matching in H which covers the
vertices of W \Gamma1 . let W 0 denote the set of vertices covered by F 0 . Define a maximal sequence
is obtained from (W
follows: suppose there exists x 62 W i\Gamma1 such that jN(x)"W is then a minimum
weight matching in H which covers W i\Gamma1 and x and, necessarily, one other vertex y. We
then take W obtained by constructing a least cost augmenting
path from x w.r.t. F
5 (whp).
Proof The proof follows from two simple claims. They can easily be justified by the
first moment method and the calculations are omitted. CLAIM 1: jW ne \Gammas=5 (whp).
CLAIM 2: S ' X [ Y; jSj - 3ne \Gammas=5 implies that (whp), in H 1 contains fewer
than 2jSj edges.
Assume the conditions of the above two claims. Then jW
contains at least is=4 edges. If jW j - 3ne \Gammas=5 then r, the number
of pairs of verttices adjoined to W 0 in constructing the set W , is greater than or equal to
has at most 3ne \Gammas=5 vertices and contains at least r 0 s=4
edges, contradicting CLAIM 2. 2
We then take . The sub-process of constructing A involves
counting the edges directed into Y n B from each vertex x 2 X n A, but does not depend
at all on which particular vertices in Y n B are adjacent to x. Thus, N(x) " (Y n B) is of
cardinality at least s=4, and it is a random set, in the sense that the probability that it is
equal to a given subset of Y n B depends only on the cardinality of that subset; moreover,
there is no dependency among the distinct sets N(x) " (Y n B) as x ranges over X n A.
Similar statements can be made about the sets N(y) " (X n A), for y 2 Y n B. There are
also no dependencies between these two collections of sets. Furthermore, in constructing
W using the augmenting path approach, we did not need to consider the cost of any edge
with both its endpoints in H \Gamma W . Thus, each such edge is still an in, out, or patch edge
with probability h.
5 Construction of an Optimal Assignment
The subgraph of induced by (X n has a perfect matching (whp).
Proof Recall that a random k-out bipartite graph on the vertex set X [ Y , where X and
Y are disjoint n-element sets, is constructed by having each vertex in X choose k random
neighbors in Y , and each vertex in Y choose k random neighbors in X . The proof follows
immediately from Walkup's result [Wal2] that a random k-out bipartite graph has a perfect
matching (whp) for any k - 2. 2
Thus, we can obtain an optimal assignment (whp) by combining an optimal matching
covering A[B with a perfect matching in the subgraph of H 1 [H 2 induced by (XnA)[(Y nB)
6 Structure of the Optimal Assignment
In this section we show that, if M is a random instance of the AP, then, with suitable
implementation, the construction of an optimal assignment based on Lemma 2 yields a
random permutation. Define the equivalence class of a matrix M as the set of all matrices
obtained by permuting the columns of M . A typical member of this equivalence class,
corresponding to the permutation -, is the matrix M - defined by m -
for a negligible fraction of the matrices in U N
(namely, those with two equal
the equivalence class of M consists of n! distinct and equiprobable matrices. Let oe be the
optimal assignment for M obtained by the algorithm described above. Then -oe is an optimal
assignment for M - . Moreover, the algorithm for constructing the optimal assignment can
be implemented so that
ffl if oe is the optimal assignment constructed for M , then -oe is the optimal assignment
constructed for
ffl A, the set of troublesome rows for M , is also the set of troublesome rows for M - .
One way to ensure this is to permute the columns of M into lexicographic order, find the
set of troublesome rows and an optimal assignment in the resulting matrix, and then permute
the columns back. For any fixed oe, as - ranges over all permutations of f1;
-oe also ranges over all permutations of f1; ng. Since all the matrices in [M ] are
equally likely, we have established that the permutation produced by the optimal assignment
algorithm described above is equally likely to be any permutation.
We note some facts about random permutations. Let oe be drawn at random from the
set of permutations of f1; ng. Then
ffl oe has at most 2 ln n cycles (whp);
ffl For all k,there are fewer than w(n) k cycles of length k (whp);
ffl There are at most n
vertices on cycles of length at most n
(whp).
Now let oe be the optimal assignment selected by our algorithm. Then
No cycle of oe has more than one-tenth of its vertices in W (whp).
Proof Conditioning on the event that M lies in a particular equivalence class, oe is
equally likely to be any permutation, while A is a fixed set of very small cardinality (whp).
A straightforward calculation shows that no cycle has more than one-twentieth of its vertices
in A (whp). Indeed, given jAj = a - 3ne \Gammas=5 , the expected number of cycles containing so
many members of A is at most
!/
a
dk=20e
' a
A similar argument applies to B. 2
7 Elimination of Small Cycles
Call a cycle in a permutation small if it contains fewer than n
vertices. We now show
how the out-edges and in-edges are used to convert the original optimal assignment into an
optimal assignment in which no cycle is small. Our procedure is to take each small cycle of
the original optimal assignment oe in turn and try to remove it without creating any new
small cycles. During its execution our algorithm will designate a vertex as dirty when its
out-edges or in-edges have been observed, so that they may no longer be considered random.
The initial set of dirty vertices is the set W defined above. A vertex that is not dirty will
be called clean. If i is clean then, independently for each j, ! is an out-edge with
probability s
is an in-edge with probability s
. Throughout the computation,
we will maintain the property that at least nine-tenths of the vertices in any remaining
short cycle are clean.
We now describe the rotation-closure algorithm that is used to eliminate one small
cycle. Let C be a small cycle of length k in the current optimal assignment. Let -
min(d 9k
clean vertices on C. We make up to - k separate attempts to
remove C. The ith attempt consists of an Out Phase and an In Phase. Let v i be the ith of
the - k clean vertices selected from C, and let u i be the predecessor of v i on C.
7.1 The Out Phase
Define a near-cycle-cover as a digraph ' consisting of a directed path P ' ending at a clean
vertex plus a set of vertex-disjoint directed cycles covering the vertices not in P ' . We obtain
an initial near-cycle-cover by deleting edge ! u from the current optimal assignment,
thus converting the small cycle C into a path from v i to u i . We then attempt to obtain
many near-cycle-covers by a rotation process. The state of this process is described by a
rooted tree whose nodes are near-cycle-covers, with the original near-cycle-cover at the root.
Consider a typical node ' consisting of a path P ' directed from a ' to b ' plus a cycle
cover of the remaining vertices. We obtain descendants of ' by looking at out-edges directed
from b ' . Consider an edge that is directed from b ' to a vertex y whose predecessor x is
clean. Such an edge is successful if either y lies on a large cycle or y lies on P ' and the
subpaths of P ' from a ' to x and from y to b ' are both of length at least n
. In such cases
a descendant of ' is created by deleting ! x; y ? and inserting ! b ' ; y ?. Once node ' has
been examined, b ' is permanently marked dirty. The tree of near-cycle-covers is grown in a
breadth-first manner until the number of leaves reaches
We shall show later that the number of vertices marked dirty throughout the entire
algorithm is o(n) (whp). Assuming this, noting that each path P ' ends in a clean vertex
assuming that the number of vertices on short cycles is less than n
(this is true
(whp)) the number of descendants of node ' is a random variable whose distribution is
and the random variables associated with distinct nodes are
independent. Suppose that level t of the rooted tree describing the Out Phase has a vertices.
Then, applying a Chernoff bound on the tails of the binomial distribution, the number of
nodes at level t lies between asand 2as, with probability greater than or equal to
. Hence the probability that the Out Phase fails to produce m leaves is (quite
conservatively) at mostX
7.2 The In Phase
The tree produced by an Out Phase has m terminal nodes. Each of these is a near-cycle-
cover in which the directed path begins at v i . Let the jth terminal node be denoted G j ,
and let the directed path in G j run from v i to x j . During the In Phase we grow rooted
trees independently from all the G j , m. The process is like the Out Phase,
except that, in computing the descendants of a node ', we fan backwards along in-edges,
rather than forwards along out-edges. For example, if a node ' with a path P ' from a ' to
x j is encountered, then we look for in-edges of the form ! x; a ' ? such that x does not lie
on a short cycle and y, the successor of x in G ' , is clean. We then create a descendant by
deleting ! x; y ? and inserting ! x; a ' ?, provided that this substitution does not create a
path or cycle of length less than n
. Once the descendants of ' have been computed, the
node a ' is permanently marked dirty.
Suppose that S 1 are the near-cycle-covers produced by the Out Phase. We
describe a two-stage process for producing the near-cycle-covers of the In Phase which is
equivalent to that described in the previous paragraph. In the first stage, imagine that we
grow the trees allowing small cycles to be produced and only ensuring that edges from clean
vertices are used. Each tree is grown to a depth ' where (w=2) ' - m. The following is true
for each tree, and each depth t ! ', the ratio between the number of nodes of depth
and the number of nodes of depth t lies between w=2 and 2w. The parameter ' is
chosen so that even if each non-leaf has only w=2 descendants, the tree will still have at
least m leaves. Let \Sigma j denote the set of initial vertices of the paths of the near-cycle-covers
created from S j in this way. We show that \Sigma In fact let \Sigma (t)
j denote the
set of start vertices of the paths at level t in the j'th tree. Clearly \Sigma (0)
so assume inductively that we have \Sigma (t)
then the clean vertices
whose in-edges are directed into \Sigma (t)
are the same as the clean vertices \Sigma (t+1)
whose
in-edges are directed into \Sigma (t). This completes the inductive step. We see also that from
this construction the number of vertices marked dirty by this stage is at most (2w) ' and
then it is easy to see that the total number of dirty vertices produced is O(n :5+o(1) ). It
follows from our analysis of the Out Phase that if E denotes the event "we fail to produce
trees in the first stage", then
We do not have to multiply the right-hand-side of (1) by m because the construction above
succeeds for all S j if and only if it succeeds for S 1 . In the second stage we prune the m trees
we have produced by deleting any edge which involved the construction of a small cycle.
For be the pruned tree grown from root G j during the two stages.
Thus T j is what we would get from G j if we had followed the procedure described in the
second paragraph of this section.
Let us call T j good if it has m leaves, and bad otherwise. Since the number of vertices
marked dirty during the entire computation is o(n), by the same analysis that was applied
to the Out Phase, the probability that an individual T j is bad is less than or equal to e \Gamma w
20 .
Thus the expected number of bad trees is at most me \Gamma w
20 and, by Markov's inequality, the
probability that the number of bad trees is at least m=2 is bounded above by 2e \Gamma w
20 . Thus,
Pr
mgood trees
mbad trees
Assuming that The Out Phase succeeds in creating a rooted tree with m leaves, and
that at least half of the m trees T j created during the In Phase are good, we now have
at least m=2 sets, each consisting of m near-cycle-covers. In the set associated with
each near-cycle-cover consists of a path ending at x j , together with a cycle cover of the
remaining vertices. The m paths have distinct starting points. Since the out-edges from
x are unconditioned, the probability that none of the m 2paths is closed by an out-edge is
bounded above by
. Thus, with probability at least 1
, one of these
paths can be closed with an out-edge, and doing so creates an optimal assignment with
one short cycle less than the optimal assignment that existed at the beginning of the Out
Phase. Thus the probability that the tth attempt at removing C fails given that the first
attempts have also failed can be bounded by, say, e \GammaAw for some absolute constant
A ? 0. Since we make -
k attempts, the probability that we fail to remove all short cycles is
at most
bln
ne \GammaAw ln
8 The Patching Process
At the start of the patching process we have an optimal assignment without small cycles,
and the patch edges are unobserved, and thus unconditioned, except for those incident with
the set of vertices Bg. Suppose we start with cycles C
each of which contains at least n
vertices. We describe a procedure that attempts to patch
these cycles together to form a tour. The basic operation of patching together two cycles
C and C 0 is as follows. Suppose cycle C contains an edge ! a 1 ; a 2 ? and cycle C 0 contains
an edge are both patch edges then we can combine
C and C 0 into a single cycle by deleting ! a inserting ! a
We attempt to create a tour by repeatedly patching cycles together in
this way. We describe a generic step in which, having patched C
to form a cycle C, we try to patch C s and C together. There are at most 3ne \Gamma s
5 vertices
in W on C s [ C. Independently, for each pair consisting of an unconditioned vertex on C s
and an unconditioned vertex on C, a patch edge is present with probability s=n. Thus,
the probability that there is no pair of edges that will patch C s and C together is bounded
above by
5 ) . This is less than or equal to e \Gammaw+o(1) .Hence
the probability that the patching process fails is bounded above by p
we
We have now completed the entire proof of Theorem 1.
9 The Proofs of Theorems 2 and 3
In proving Theorems 2 and 3, we shall describe the generation of our matrix M , the corresponding
bipartite graph H , and the directed graph G in a slightly different manner.
We first generate a random n \Theta n matrix N where each entry is drawn uniformly from
these choices are independent (note that in order to combine Theorems
2 and 3 we insist only that c n is either constant or goes to infinity with n). We then
randomly choose a permutation \Pi of f1; :::; ng with each permutation equally likely. We
obtain M by setting m is the entry in the i th row and j th column
of N ). Proceeding in this fashion rather than choosing the elements of M directly makes
certain assertions about the independence of events obvious. We let H 0 be the bipartite
graph which corresponds to N in the same way that H corresponds to M . We note that if
we choose some optimal matching in H 0 then the corresponding matching in M will have
the cycle cover of a random permutation.
We now need some definitions. So, consider an arbitrary matrix N and corresponding
bipartite subgraph H 0 . By a forced edge of H 0 we mean an edge which is in every optimal
matching in H 0 . By a positive edge we mean an edge which is in some optimal matching
of H 0 and has weight at least one. The first step in proving Theorems 2 and 3 is to note
that if a particular weighting has a lot of forced edges then probably it will not satisfy
In particular if all the edges are forced then the probability that
n .
The precise result we will need is that if for some weighting the corresponding H 0 has s
forced edges then the probability that the corresponding cycle cover has a non-hamiltonian
cycle made up only of forced edges - a forced cycle - is the same as it would be if we took a
random cycle cover and then chose s edges at random and called them forced. This follows
from the manner in which we generate M . It is convenient now to give a lower bound for
the probability - t;n that a random cycle cover has a cycle of length at most t, (more precise
esitmates are available, see for example Bollob'as [B]). We will use - t;n
t+1 . To see
this use induction on
which is a consequence of the fact that the size of the cycle containing 1 is uniformly
distributed. The following lemma then follows easily. For any weighting of N such that
H 0 has s forced edges, the probability that the corresponding weighting of M has a forced
cycle of size at most t and hence AP (M) 6= ATSP (M) is at least
ae'
t is an integer between 1 and n
oe
The second step in the proof is to note that most weightings will have many positive edges
because many vertices of G will not be the tail of any arc of cost zero. In fact since the
probability that x is such a vertex is
The expected number of
positive edges for a random weighting is at least
. The key to the proof, is the following lemma which links these two results. The
expected number of forced edges in a random weighting is at least (and essentially equal
to) the expected number of positive edges. Combining Lemmas 9 and 9, we obtain that
the expected number of forced edges is at least (1 Theorem 2 then follows
immediately from Lemma 9, on taking
Pr(forced cycle of length at most 2)
by Jensen's Inequality
2e \Gamma2=cAgain combining Lemmas 9, 9 and 9 we see that if c n tends to infinity with n then Theorem
3 follows from
Pr(forced cycle of length at most t)
n).
One can tighten Theorem 2 slightly by insisting that the solution to AP (M) contains
no 1-cycles. Thus let D(M) denote problem AP (M) with the added constraint that the
permutation should contain no 1-cycles i.e.be a derangement. If the solution to AP (M) is
a derangement then it also solves D(M) and the probability of this tends to e \Gamma1 . Since
forced edges occur independently of the cycle structure we can see that
The question of whether or not Theorem 3 can be similarly strengthened remains open.
The answer is almost certainly yes, but how to prove it?
It remains only to prove Lemma 6. To prove Lemma 6, we give an injective mapping
from the (weighting, positive edge) pairs to the (weighting, forced edge) pairs. This implies
the result. Indeed, let
e ) denote the set of weightings in which
e is a positive (resp. forced) edge. Then
\Gamman
e
\Gamman
e
e j as will be shown
E(number of positive edges):
It only remains to show that
e j for all edges e. Now, given a positive edge e in a
weighting W , we obtain a new weighting W 0 by reducing the weight on e by 1 and leaving all
other weights the same. We note that the cost of an optimal matching with respect to W 0 is
one less than the cost of an optimal matching with respect to W and any optimal matching
with respect to W 0 must use e. In our mapping, we map (W; e) to (W 0 ; e). Clearly, this
gives the desired injection. This completes the proof of Lemma 6 and the two theorems.
We note that our injection is almost a bijection because adding one to a forced edge yields
a positive edge in a new matching unless the forced edge has weight bc n nc, surely a rare
occurrence.



--R

Branch and bound methods

On patching algorithms for random asymmetric travelling salesman problems
An algorithm for finding hamilton cycles in random digraphs
A patching algorithm for the non-symmetric traveling salesman prob- lem
Probabilistic analysis of heuristics in The traveling salesman problem: a guided tour of combinatorial optimization
Exact solution of large asymmetric traveling salesman problems
On the expected value of a random assignment problem
Matchings in random regular bipartite graphs
--TR

--CTR
Alan Frieze , Gregory B. Sorkin, The probabilistic relationship between the assignment and asymmetric traveling salesman problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.652-660, January 07-09, 2001, Washington, D.C., United States
L. Sunil Chandran , L. Shankar Ram, On the relationship between ATSP and the cycle cover problem, Theoretical Computer Science, v.370 n.1-3, p.218-228, February, 2007
probabilistic analysis;traveling salesman