59:
which are in one but not the other; new tours are built by reassembling pieces of the old tour in a different order, sometimes changing the direction in which a sub-tour is traversed. Lin–Kernighan is adaptive and has no fixed number of edges to replace at a step, but favours small numbers such as 2
6471:
TSP, the idea of using positive gain alternating trails to find favourable exchanges is less useful, because there are fewer ways in which pieces of a tour can be rearranged to yield new tours when one may not reverse the orientation of a piece. Two pieces can only be patched together to reproduce
6459:
exchanges for those that are described by a single alternating trail. The smallest non-sequential exchange would however replace 4 edges and consist of two cycles of 4 edges each (2 edges added, 2 removed), so it is long compared to the typical Lin–Kernighan exchange, and there are few of these
6463:
In at least one implementation by Lin & Kernighan there was an extra final step considering such non-sequential exchanges of 4 edges before declaring a tour locally optimal, which would mean the tours produced are 4-opt unless one introduces further constraints on the search (which Lin and
6472:
the original tour. Three pieces can be patched together to form a different tour in one way only, and the corresponding alternating trail does not extend to a closed trail for rearranging four pieces into a new tour. To rearrange four pieces, one needs a non-sequential exchange.
6794:
as the time complexity for this check, since it is necessary to walk around the full tour before being able to determine that it is in fact a
Hamiltonian cycle. That is too slow for the second usage of this test, which gets carried out for every alternating trail with more than
3663:
As an enumeration algorithm this is slightly flawed, because it may report the same trail multiple times, with different starting points, but Lin–Kernighan does not care because it mostly aborts the enumeration after finding the first hit. It should however be remarked that:
47:) as part of the input and attempt to improve it by searching in the neighbourhood of the given tour for one that is shorter, and upon finding one repeats the process from that new one, until encountering a local minimum. As in the case of the related
6716:
7023:
2417:
starting at other vertices but backed out because some subtrail failed the positive gain constraint.) Reducing the number of branches to explore translates directly to a reduction in runtime, and the sooner a branch can be pruned, the better.
5243:
5525:
660:
5102:
4850:
2994:
1340:
5928:
3544:
486:
5655:
3278:
2808:
1224:
1951:
6005:
4930:
3839:
is an upper bound on the length of the alternating trail after backtracking; beyond this depth, the algorithm explores at most one way of extending the alternating trail. Standard value is that
3650:
3071:
1168:
3905:
is an alternating path length beyond which it begins to be required that closing the current trail (regardless of the gain of doing so) yields an exchange to a new tour. Standard value is that
2292:
1567:
219:
4127:
in the average overall running time for their algorithm, but other implementors have had trouble reproducing that result. It appears unlikely that the worst-case running time is polynomial.
2071:
100:
of the travelling salesman problem, tours are uniquely determined by their sets of edges, so we may as well encode them as such. In the main loop of the local search, we have a current tour
6433:
3997:
177:
6161:
1850:
3719:
Lin–Kernighan also restricts the search in various ways, most obviously regarding the search depth (but not only in that way). The above unrestricted search still terminates because at
1528:
762:
527:
6506:
5393:
4201:
3714:
1660:
1026:
943:
269:
135:
4065:
5720:
1790:
5760:
4727:
4541:
4284:
3376:
3336:
2871:
2586:
2498:
6508:
at two points: obviously when deciding whether a better tour has been found, but also as a constraint to descending in the search tree, as controlled via the infeasibility depth
4379:
5328:
3151:
314:
2001:
3805:
The basic form of the Lin–Kernighan algorithm not only does a local search counterpart of the above enumeration, but it also introduces two parameters that narrow the search.
4501:
2205:
7124:
5805:
3421:
2120:
2238:
6574:
6901:
4963:
6277:
6201:
6122:
5107:
2153:
978:
7315:
7279:
7190:
6569:
4659:
4475:
2701:
1710:, one is exploring a search tree of alternating trails. The key idea of the Lin–Kernighan algorithm is to remove from this tree all alternating trails which have gain
6337:
6244:
6082:
6053:
5398:
4626:
4579:
4310:
4247:
3936:
3870:
3794:
2668:
2624:
2524:
2461:
1592:
1445:
895:
850:
705:
379:
7220:
7154:
1731:
7075:
6533:
6394:
no more than one way of extending the current trail is considered, which in principle stops those explorations from raising the exponent in the runtime complexity.
6392:
4429:
4164:
4024:
3903:
3836:
2395:
2348:
98:
6792:
3746:
3573:
2321:
4105:
7243:
785:
7043:
6896:
6876:
6856:
6833:
6813:
6763:
6740:
6453:
6362:
5273:
4684:
4402:
4330:
4125:
4085:
3766:
3686:
3096:
2831:
2544:
2415:
2368:
1870:
1708:
1680:
1632:
1612:
1491:
1420:
1400:
1380:
1360:
1244:
1117:
1097:
1077:
1053:
998:
915:
870:
825:
805:
725:
680:
547:
354:
334:
6838:
A useful degree of freedom here is that one may choose the order in which step 2.3.2 iterates over all vertices; in particular, one may follow the known tour
4968:
6464:
Kernighan in fact did). The literature is vague on exactly what is included in the Lin–Kernighan heuristic proper, and what constitutes further refinements.
4732:
2876:
556:
5810:
3426:
387:
3796:, so rather than actually listing all siblings in the search tree before exploring the first of them, one may wish to generate these siblings lazily.
1253:
5530:
1690:
Alternating trails (closed or open) are built by extending a shorter alternating trail, so when exploring the neighbourhood of the current tour
3159:
7504:
6742:, so what needs to be determined is whether that 2-factor consists of a single Hamiltonian cycle, or instead is made up of several cycles.
16:
This article is about the heuristic for the travelling salesman problem. For a heuristic algorithm for the graph partitioning problem, see
7489:
4026:, and the final round of the algorithm may have to check all of them before concluding that the current tour is locally optimal, we get
2706:
7494:
2323:. Here the lemma implies that there for every closed alternating trail with positive gain exists at least one starting vertex
1880:
6435:
of two tours need not be, so in general this method of alternating trails cannot explore the full neighbourhood of a trail
1852:, then there is a cyclic permutation of these numbers such that all partial sums are positive as well, i.e., there is some
7499:
1173:
7317:
is concerned, the outcome of this test can be inherited information rather than something that has to be computed fresh.
5933:
4858:
3578:
2999:
1122:
17:
2243:
40:
36:
2011:
3945:
6367:
The length of the alternating trails considered are thus not explicitly bounded, but beyond the backtracking depth
24:
7353:
Papadimitriou, C. H. (1992). "The complexity of the Lin–Kernighan heuristic for the travelling salesman problem".
6132:
1795:
1533:
185:
7334:
Melamed, I. I.; Sergeev, S. I.; Sigal, I. Kh. (1989). "The traveling salesman problem. Approximate algorithms".
1496:
730:
495:
6405:
140:
6483:
5333:
4169:
3691:
1637:
1003:
920:
103:
4029:
5660:
2421:
This yields the following algorithm for finding all closed, positive gain alternating trails in the graph.
1743:
7416:
5728:
4695:
4509:
4252:
3344:
3283:
2839:
2554:
2466:
4338:
224:
6719:
6402:
The closed alternating trails found by the above method are all connected, but the symmetric difference
5281:
3104:
274:
1956:
1733:. This does not prevent finding every closed trail with positive gain, thanks to the following lemma.
7407:
K. Helsgaun (2000). "An
Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic".
6711:{\displaystyle T\mathbin {\triangle } \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{2k}v_{2k+1},v_{2k+1}v_{0}\}}
4480:
2158:
1032:
180:
7421:
7080:
7018:{\displaystyle {\bigl (}\mathrm {V} (G),T\setminus \{v_{0}v_{1},\dotsc ,v_{2k-2}v_{2k-1}\}{\bigr )}}
5765:
3381:
2076:
5238:{\displaystyle T\mathbin {\triangle } \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i},v_{i}u,uv_{0}\}}
2210:
56:
32:
4935:
6249:
6173:
6094:
5520:{\displaystyle T\mathbin {\triangle } \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i},v_{i}v_{0}\}}
2125:
948:
7446:
7379:
7284:
7248:
7159:
6835:. If keeping track of more information, the test can instead be carried out in constant time.
6538:
4631:
4447:
2673:
44:
6309:
6211:
6061:
6020:
4593:
4546:
4289:
4214:
3908:
3842:
2635:
2591:
2503:
2428:
7426:
7395:
7362:
7195:
7129:
1713:
7048:
6511:
6370:
4407:
4137:
4087:) as a lower bound on the exponent of the algorithm complexity. Lin & Kernighan report
4002:
3881:
3814:
2373:
2326:
980:. It is however easier to do those tests in the opposite order: first search for plausible
71:
7383:
6768:
3722:
3549:
2297:
7439:
4090:
7225:
5097:{\displaystyle uv_{0}\notin T\cup \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i},v_{i}u\}}
3774:
1572:
1425:
875:
830:
767:
685:
359:
7028:
6881:
6861:
6841:
6818:
6798:
6748:
6725:
6438:
6347:
5258:
4669:
4387:
4315:
4110:
4070:
3751:
3671:
3081:
2816:
2529:
2400:
2353:
1855:
1693:
1665:
1617:
1597:
1454:
1405:
1385:
1365:
1345:
1229:
1102:
1082:
1062:
1038:
983:
900:
855:
810:
790:
710:
665:
532:
339:
319:
7430:
7483:
1448:
1247:
2370:
will be found when the search explores the branch of alternating trails starting at
4845:{\displaystyle v_{i}u\in T\setminus \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i}\}}
2989:{\displaystyle v_{i}u\in T\setminus \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i}\}}
655:{\displaystyle g(T\mathbin {\triangle } T')=\sum _{e\in T}c(e)-\sum _{e\in T'}c(e)}
55:
algorithms, the relevant measure of "distance" between two tours is the number of
7474:
7469:
5923:{\displaystyle v_{i}u\notin T\cup \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i}\}}
3668:
Lin–Kernighan is not satisfied with just having found a closed alternating trail
3539:{\displaystyle v_{i}u\notin T\cup \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i}\}}
481:{\displaystyle g(F)=\sum _{e\in F\cap T}c(e)-\sum _{e\in F\setminus T}c(e)\quad }
7386:(1973). "An Effective Heuristic Algorithm for the Traveling-Salesman Problem".
1335:{\displaystyle G={\bigl (}\mathrm {V} (G),T\mathbin {\triangle } T'{\bigr )}}
7464:
5650:{\displaystyle F:=\{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i},v_{i}v_{0}\}}
7399:
3273:{\displaystyle \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i},v_{i}v_{0}\}}
7045:
paths. The outcome of the
Hamiltonicity test done when considering the
2350:
for which all the gains of the partial trails are positive as well, so
4404:
of exchange edges found for current tour, and its corresponding gain
7440:"The Traveling Salesman Problem: A Case Study in Local Optimization"
7366:
6745:
If naively posing this subproblem as giving a subroutine the set of
6480:
The Lin–Kernighan heuristic checks the validity of tour candidates
2397:. (Prior to that the search may have considered other subtrails of
1662:
into a tour; it could alternatively turn out to be a disconnected
52:
48:
2803:{\displaystyle F=\{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i}\}}
1402:
only, and at each vertex there are as many incident edges from
6455:. The literature on the Lin–Kernighan heuristic uses the term
1594:
may thus be found by enumerating closed alternating trails in
1926:
3771:
In most iterations one wishes to quickly find a better tour
1946:{\displaystyle \sum _{i=0}^{r}a_{(k+i){\bmod {n}}}>0}
6535:. Concretely, at larger depths in the search a vertex
3768:, but that is far beyond what is practical to explore.
7287:
7251:
7245:
different cases as part of performing step 2.3.2 for
7228:
7198:
7162:
7132:
7083:
7051:
7031:
6904:
6884:
6864:
6844:
6821:
6801:
6771:
6751:
6728:
6718:
is a tour. By design that set of edges constitutes a
6577:
6541:
6514:
6486:
6441:
6408:
6373:
6350:
6312:
6252:
6214:
6176:
6135:
6097:
6064:
6023:
5936:
5813:
5768:
5731:
5663:
5533:
5401:
5336:
5284:
5261:
5110:
4971:
4938:
4861:
4735:
4698:
4672:
4634:
4596:
4549:
4512:
4483:
4450:
4410:
4390:
4341:
4318:
4292:
4255:
4217:
4172:
4140:
4113:
4093:
4073:
4032:
4005:
3948:
3911:
3884:
3845:
3817:
3777:
3754:
3725:
3694:
3674:
3581:
3552:
3429:
3384:
3347:
3286:
3162:
3107:
3084:
3002:
2879:
2842:
2819:
2709:
2676:
2638:
2594:
2557:
2532:
2506:
2469:
2431:
2403:
2376:
2356:
2329:
2300:
2246:
2213:
2161:
2128:
2079:
2014:
1959:
1883:
1858:
1798:
1746:
1716:
1696:
1668:
1640:
1620:
1600:
1575:
1536:
1499:
1457:
1428:
1408:
1388:
1368:
1348:
1256:
1232:
1176:
1125:
1105:
1085:
1065:
1041:
1006:
986:
951:
923:
903:
878:
858:
833:
813:
793:
770:
733:
713:
688:
668:
559:
535:
498:
390:
362:
342:
322:
277:
227:
188:
143:
106:
74:
1449:
Hierholzer's algorithm for finding
Eulerian circuits
1219:{\displaystyle {\bigl (}\mathrm {V} (G),T'{\bigr )}}
6000:{\displaystyle {\bigl (}u,i+1,g-c(v_{i}u){\bigr )}}
4925:{\displaystyle {\bigl (}u,i+1,g+c(v_{i}u){\bigr )}}
3645:{\displaystyle {\bigl (}u,i+1,g-c(v_{i}u){\bigr )}}
3066:{\displaystyle {\bigl (}u,i+1,g+c(v_{i}u){\bigr )}}
1163:{\displaystyle {\bigl (}\mathrm {V} (G),T{\bigr )}}
7309:
7273:
7237:
7214:
7184:
7148:
7118:
7069:
7037:
7017:
6890:
6870:
6850:
6827:
6807:
6786:
6757:
6734:
6710:
6563:
6527:
6500:
6447:
6427:
6386:
6356:
6331:
6271:
6238:
6195:
6155:
6116:
6076:
6047:
5999:
5922:
5799:
5754:
5714:
5649:
5519:
5387:
5322:
5267:
5237:
5096:
4957:
4924:
4844:
4721:
4678:
4653:
4620:
4573:
4535:
4495:
4469:
4423:
4396:
4373:
4324:
4304:
4278:
4241:
4195:
4158:
4119:
4099:
4079:
4059:
4018:
3991:
3930:
3897:
3864:
3830:
3788:
3760:
3748:there is no longer any unpicked edge remaining in
3740:
3708:
3680:
3644:
3567:
3538:
3415:
3370:
3330:
3272:
3145:
3090:
3065:
2988:
2865:
2825:
2802:
2695:
2662:
2618:
2580:
2538:
2518:
2492:
2455:
2409:
2389:
2362:
2342:
2315:
2286:
2232:
2199:
2147:
2114:
2065:
1995:
1945:
1864:
1844:
1784:
1725:
1702:
1674:
1654:
1626:
1606:
1586:
1561:
1522:
1485:
1439:
1414:
1394:
1374:
1354:
1334:
1238:
1218:
1162:
1111:
1091:
1071:
1047:
1020:
992:
972:
945:is again a tour, looking for such a set which has
937:
909:
889:
864:
844:
819:
799:
779:
756:
719:
699:
674:
654:
541:
521:
480:
373:
348:
328:
308:
263:
213:
171:
129:
92:
6055:be the top element on the stack (peek, not pop).
4312:is the current number of edges in the trail, and
2526:is the current number of edges in the trail, and
7453:. London: John Wiley and Sons. pp. 215–310.
4130:In terms of a stack as above, the algorithm is:
3688:of positive gain, it additionally requires that
2287:{\displaystyle \sum \nolimits _{i=0}^{n-1}a_{i}}
1493:decomposes into closed alternating trails. Sets
4166:of the travelling salesman problem, and a tour
2066:{\displaystyle F=e_{0}\,e_{1}\,\dots \,e_{n-1}}
6460:compared to the full set of 4-edge exchanges.
3992:{\displaystyle O(n^{\lfloor p_{1}/2\rfloor })}
7126:depends only on in which of these paths that
7010:
6907:
6571:is only appended to the alternating trail if
5992:
5939:
4917:
4864:
4381:of vertices in the current alternating trail,
3637:
3584:
3058:
3005:
1614:, even if not every closed alternating trail
1327:
1287:
1211:
1179:
1155:
1128:
1000:with positive gain, and only second check if
8:
7438:Johnson, David S.; McGeoch, Lyle A. (1997).
7005:
6935:
6705:
6586:
5917:
5836:
5644:
5540:
5514:
5410:
5232:
5119:
5091:
4994:
4839:
4758:
4054:
4033:
3981:
3960:
3533:
3452:
3267:
3163:
2983:
2902:
2797:
2716:
381:, it is convenient to consider the quantity
6156:{\displaystyle T:=T\mathbin {\triangle } F}
1845:{\displaystyle \sum _{i=0}^{n-1}a_{i}>0}
1562:{\displaystyle F=T\mathbin {\triangle } T'}
214:{\displaystyle F=T\mathbin {\triangle } T'}
7451:Local Search in Combinatorial Optimization
7222:. Hence it would be sufficient to examine
6163:(update current tour) and clear the stack.
1523:{\displaystyle F\subseteq \mathrm {E} (G)}
757:{\displaystyle F\subseteq \mathrm {E} (G)}
522:{\displaystyle F\subseteq \mathrm {E} (G)}
7420:
7292:
7286:
7256:
7250:
7227:
7203:
7197:
7167:
7161:
7137:
7131:
7101:
7088:
7082:
7050:
7030:
7009:
7008:
6990:
6971:
6952:
6942:
6912:
6906:
6905:
6903:
6883:
6863:
6843:
6820:
6800:
6770:
6750:
6727:
6699:
6680:
6658:
6645:
6626:
6616:
6603:
6593:
6581:
6576:
6546:
6540:
6519:
6513:
6490:
6485:
6440:
6428:{\displaystyle T\mathbin {\triangle } T'}
6412:
6407:
6378:
6372:
6349:
6317:
6311:
6263:
6251:
6213:
6187:
6175:
6145:
6134:
6102:
6096:
6063:
6022:
5991:
5990:
5978:
5938:
5937:
5935:
5911:
5895:
5876:
5866:
5853:
5843:
5818:
5812:
5785:
5767:
5738:
5730:
5703:
5693:
5668:
5662:
5638:
5628:
5615:
5599:
5580:
5570:
5557:
5547:
5532:
5527:is a tour (Hamiltonicity check) then let
5508:
5498:
5485:
5469:
5450:
5440:
5427:
5417:
5405:
5400:
5379:
5363:
5353:
5335:
5311:
5301:
5283:
5260:
5226:
5207:
5194:
5178:
5159:
5149:
5136:
5126:
5114:
5109:
5082:
5069:
5053:
5034:
5024:
5011:
5001:
4979:
4970:
4949:
4937:
4916:
4915:
4903:
4863:
4862:
4860:
4833:
4817:
4798:
4788:
4775:
4765:
4740:
4734:
4705:
4697:
4671:
4639:
4633:
4595:
4548:
4519:
4511:
4482:
4455:
4449:
4415:
4409:
4389:
4359:
4346:
4340:
4317:
4291:
4262:
4254:
4216:
4179:
4171:
4139:
4112:
4092:
4072:
4046:
4040:
4031:
4010:
4004:
3973:
3967:
3959:
3947:
3916:
3910:
3889:
3883:
3850:
3844:
3822:
3816:
3776:
3753:
3724:
3698:
3693:
3673:
3636:
3635:
3623:
3583:
3582:
3580:
3551:
3527:
3511:
3492:
3482:
3469:
3459:
3434:
3428:
3401:
3383:
3354:
3346:
3313:
3303:
3285:
3261:
3251:
3238:
3222:
3203:
3193:
3180:
3170:
3161:
3134:
3124:
3106:
3083:
3057:
3056:
3044:
3004:
3003:
3001:
2977:
2961:
2942:
2932:
2919:
2909:
2884:
2878:
2849:
2841:
2818:
2791:
2775:
2756:
2746:
2733:
2723:
2708:
2681:
2675:
2637:
2593:
2564:
2556:
2531:
2505:
2476:
2468:
2430:
2402:
2381:
2375:
2355:
2334:
2328:
2299:
2278:
2262:
2251:
2245:
2218:
2212:
2188:
2166:
2160:
2133:
2127:
2103:
2084:
2078:
2051:
2046:
2042:
2036:
2031:
2025:
2013:
1958:
1929:
1925:
1909:
1899:
1888:
1882:
1857:
1830:
1814:
1803:
1797:
1770:
1751:
1745:
1715:
1695:
1667:
1644:
1639:
1619:
1599:
1574:
1546:
1535:
1506:
1498:
1467:
1456:
1427:
1407:
1387:
1367:
1347:
1326:
1325:
1312:
1292:
1286:
1285:
1266:
1255:
1231:
1210:
1209:
1184:
1178:
1177:
1175:
1154:
1153:
1133:
1127:
1126:
1124:
1104:
1084:
1064:
1040:
1010:
1005:
985:
950:
927:
922:
902:
877:
857:
832:
812:
792:
769:
740:
732:
712:
687:
667:
623:
592:
569:
558:
534:
505:
497:
447:
410:
389:
361:
341:
321:
282:
276:
232:
226:
198:
187:
172:{\displaystyle T'\subset \mathrm {E} (G)}
155:
142:
113:
105:
73:
7409:European Journal of Operational Research
6501:{\displaystyle T\mathbin {\triangle } F}
5388:{\displaystyle g-c(v_{i}v_{0})>g^{*}}
4196:{\displaystyle T\subset \mathrm {E} (G)}
3709:{\displaystyle T\mathbin {\triangle } F}
3575:of these, or there could be none), push
3280:as a closed alternating trail with gain
1655:{\displaystyle T\mathbin {\triangle } F}
1021:{\displaystyle T\mathbin {\triangle } F}
938:{\displaystyle T\mathbin {\triangle } F}
271:of the new tour is less than the length
130:{\displaystyle T\subset \mathrm {E} (G)}
7326:
6932:
4755:
4490:
4060:{\displaystyle \lfloor p_{1}/2\rfloor }
2996:(there are at most two of these), push
2899:
2703:. The current alternating trail is now
457:
5715:{\displaystyle g^{*}:=g-c(v_{i}v_{0})}
1119:, respectively. Because the subgraphs
727:-opt can be regarded as examining all
1785:{\displaystyle a_{0},\dotsc ,a_{n-1}}
7:
5755:{\displaystyle u\in \mathrm {V} (G)}
4722:{\displaystyle u\in \mathrm {V} (G)}
4536:{\displaystyle u\in \mathrm {V} (G)}
4436:Initialise the stack to being empty.
4279:{\displaystyle u\in \mathrm {V} (G)}
3371:{\displaystyle u\in \mathrm {V} (G)}
3331:{\displaystyle g-c(v_{i}v_{0})>0}
2866:{\displaystyle u\in \mathrm {V} (G)}
2581:{\displaystyle u\in \mathrm {V} (G)}
2493:{\displaystyle u\in \mathrm {V} (G)}
1079:) if its edges are alternatingly in
4374:{\displaystyle v_{0},v_{1},\dotsc }
2248:
662:: how much longer the current tour
264:{\displaystyle \sum _{e\in T'}c(e)}
6913:
6582:
6491:
6413:
6146:
5739:
5406:
5323:{\displaystyle g>c(v_{i}v_{0})}
5115:
4706:
4520:
4263:
4180:
3699:
3355:
3146:{\displaystyle g>c(v_{i}v_{0})}
2850:
2565:
2477:
1645:
1547:
1507:
1468:
1313:
1293:
1267:
1185:
1134:
1011:
928:
741:
570:
506:
309:{\displaystyle \sum _{e\in T}c(e)}
199:
156:
114:
14:
6765:edges as input, one ends up with
1996:{\displaystyle r=0,1,\dotsc ,n-1}
221:is not too large and the length
5245:is a tour (Hamiltonicity check)
4496:{\displaystyle F:=\varnothing }
2200:{\displaystyle a_{i}=-c(e_{i})}
2008:For a closed alternating trail
477:
336:is typically much smaller than
43:algorithms, which take a tour (
7119:{\displaystyle v_{2k}v_{2k+1}}
7064:
7052:
6923:
6917:
6781:
6775:
6233:
6215:
6042:
6024:
5987:
5971:
5800:{\displaystyle g>c(v_{i}u)}
5794:
5778:
5749:
5743:
5709:
5686:
5369:
5346:
5317:
5294:
4912:
4896:
4716:
4710:
4615:
4597:
4568:
4550:
4530:
4524:
4273:
4267:
4236:
4218:
4205:Output: a locally optimal tour
4190:
4184:
4153:
4141:
3986:
3952:
3632:
3616:
3562:
3556:
3416:{\displaystyle g>c(v_{i}u)}
3410:
3394:
3365:
3359:
3319:
3296:
3140:
3117:
3053:
3037:
2860:
2854:
2657:
2639:
2613:
2595:
2575:
2569:
2487:
2481:
2450:
2432:
2310:
2304:
2194:
2181:
2115:{\displaystyle a_{i}=c(e_{i})}
2109:
2096:
1922:
1910:
1517:
1511:
1480:
1461:
1303:
1297:
1279:
1260:
1195:
1189:
1144:
1138:
961:
955:
751:
745:
649:
643:
613:
607:
582:
563:
516:
510:
474:
468:
437:
431:
400:
394:
303:
297:
258:
252:
166:
160:
124:
118:
87:
75:
1:
7431:10.1016/S0377-2217(99)00284-2
3999:alternating trails of length
3801:Basic Lin–Kernighan algorithm
2629:While the stack is nonempty:
2233:{\displaystyle e_{i}\notin T}
1342:will have vertices of degree
137:and are looking for new tour
39:. It belongs to the class of
4107:as an empirical exponent of
7505:Travelling salesman problem
7470:Concorde TSP implementation
4958:{\displaystyle i\leq p_{2}}
316:of the current tour. Since
37:travelling salesman problem
7521:
7490:Combinatorial optimization
7336:Avtomatika i Telemekhanika
6272:{\displaystyle j>p_{1}}
6196:{\displaystyle i>p_{1}}
6117:{\displaystyle g^{*}>0}
4332:is the current trail gain,
2546:is the current trail gain.
2425:State: a stack of triples
2148:{\displaystyle e_{i}\in T}
35:for solving the symmetric
25:combinatorial optimization
15:
7355:SIAM Journal on Computing
6898:, the remaining subgraph
973:{\displaystyle g(F)>0}
7495:Combinatorial algorithms
7310:{\displaystyle v_{2k+1}}
7274:{\displaystyle v_{2k-1}}
7185:{\displaystyle v_{2k+1}}
6564:{\displaystyle v_{2k+1}}
6246:off the stack that have
4654:{\displaystyle v_{i}:=u}
4470:{\displaystyle g^{*}:=0}
2696:{\displaystyle v_{i}:=u}
1447:. Hence (essentially by
6332:{\displaystyle g^{*}=0}
6239:{\displaystyle (u,j,g)}
6077:{\displaystyle i\leq j}
6048:{\displaystyle (u,j,g)}
4621:{\displaystyle (u,i,g)}
4587:the stack is nonempty:
4574:{\displaystyle (u,0,0)}
4305:{\displaystyle i\geq 0}
4242:{\displaystyle (u,i,g)}
3931:{\displaystyle p_{2}=2}
3865:{\displaystyle p_{1}=5}
2663:{\displaystyle (u,i,g)}
2619:{\displaystyle (u,0,0)}
2519:{\displaystyle i\geq 0}
2456:{\displaystyle (u,i,g)}
18:Kernighan–Lin algorithm
7475:LK Heuristic in Python
7311:
7275:
7239:
7216:
7215:{\displaystyle v_{2k}}
7186:
7150:
7149:{\displaystyle v_{2k}}
7120:
7071:
7039:
7019:
6892:
6872:
6852:
6829:
6809:
6788:
6759:
6736:
6712:
6565:
6529:
6502:
6476:Checking Hamiltonicity
6449:
6429:
6388:
6358:
6333:
6273:
6240:
6197:
6157:
6118:
6078:
6049:
6001:
5924:
5801:
5756:
5716:
5651:
5521:
5389:
5324:
5269:
5239:
5098:
4959:
4926:
4846:
4723:
4680:
4655:
4628:off the stack and let
4622:
4575:
4537:
4497:
4471:
4425:
4398:
4375:
4326:
4306:
4280:
4243:
4197:
4160:
4121:
4101:
4081:
4061:
4020:
3993:
3932:
3899:
3866:
3832:
3790:
3762:
3742:
3710:
3682:
3646:
3569:
3540:
3417:
3372:
3332:
3274:
3147:
3092:
3067:
2990:
2867:
2827:
2804:
2697:
2670:off the stack and let
2664:
2620:
2582:
2540:
2520:
2494:
2457:
2411:
2391:
2364:
2344:
2317:
2288:
2234:
2201:
2149:
2116:
2067:
1997:
1947:
1904:
1866:
1846:
1825:
1792:are numbers such that
1786:
1727:
1726:{\displaystyle \leq 0}
1704:
1676:
1656:
1628:
1608:
1588:
1563:
1524:
1487:
1441:
1416:
1396:
1376:
1356:
1336:
1240:
1220:
1164:
1113:
1093:
1073:
1049:
1022:
994:
974:
939:
911:
891:
866:
846:
821:
801:
781:
758:
721:
701:
676:
656:
543:
523:
482:
375:
350:
330:
310:
265:
215:
173:
131:
94:
7445:. In E. H. L. Aarts;
7400:10.1287/opre.21.2.498
7312:
7276:
7240:
7217:
7187:
7151:
7121:
7072:
7070:{\displaystyle (k+1)}
7040:
7020:
6893:
6873:
6853:
6830:
6810:
6789:
6760:
6737:
6713:
6566:
6530:
6528:{\displaystyle p_{2}}
6503:
6450:
6430:
6389:
6387:{\displaystyle p_{1}}
6359:
6334:
6274:
6241:
6198:
6158:
6119:
6079:
6050:
6002:
5925:
5802:
5757:
5717:
5652:
5522:
5390:
5325:
5270:
5240:
5099:
4960:
4927:
4847:
4724:
4681:
4656:
4623:
4576:
4538:
4498:
4472:
4426:
4424:{\displaystyle g^{*}}
4399:
4376:
4327:
4307:
4281:
4244:
4198:
4161:
4159:{\displaystyle (G,c)}
4122:
4102:
4082:
4062:
4021:
4019:{\displaystyle p_{1}}
3994:
3933:
3900:
3898:{\displaystyle p_{2}}
3867:
3833:
3831:{\displaystyle p_{1}}
3791:
3763:
3743:
3711:
3683:
3647:
3570:
3541:
3418:
3373:
3333:
3275:
3148:
3093:
3068:
2991:
2868:
2828:
2805:
2698:
2665:
2621:
2583:
2541:
2521:
2495:
2458:
2412:
2392:
2390:{\displaystyle v_{0}}
2365:
2345:
2343:{\displaystyle v_{0}}
2318:
2289:
2235:
2202:
2150:
2117:
2068:
1998:
1948:
1884:
1867:
1847:
1799:
1787:
1728:
1705:
1677:
1657:
1629:
1609:
1589:
1564:
1525:
1488:
1442:
1417:
1397:
1377:
1357:
1337:
1241:
1221:
1165:
1114:
1094:
1074:
1050:
1023:
995:
975:
940:
912:
892:
867:
847:
822:
802:
782:
759:
722:
702:
682:is than the new tour
677:
657:
544:
524:
483:
376:
351:
331:
311:
266:
216:
174:
132:
95:
93:{\displaystyle (G,c)}
68:For a given instance
7500:Heuristic algorithms
7285:
7249:
7226:
7196:
7160:
7156:resides and whether
7130:
7081:
7049:
7029:
6902:
6882:
6862:
6842:
6819:
6799:
6787:{\displaystyle O(n)}
6769:
6749:
6726:
6575:
6539:
6512:
6484:
6439:
6406:
6371:
6348:
6310:
6250:
6212:
6174:
6133:
6095:
6062:
6021:
5934:
5811:
5766:
5729:
5661:
5531:
5399:
5334:
5282:
5259:
5108:
4969:
4936:
4859:
4733:
4696:
4670:
4632:
4594:
4547:
4510:
4481:
4448:
4408:
4388:
4339:
4316:
4290:
4253:
4215:
4170:
4138:
4111:
4091:
4071:
4030:
4003:
3946:
3909:
3882:
3843:
3815:
3775:
3752:
3741:{\displaystyle i=2n}
3723:
3692:
3672:
3579:
3568:{\displaystyle O(n)}
3550:
3427:
3382:
3345:
3284:
3160:
3105:
3082:
3000:
2877:
2840:
2817:
2707:
2674:
2636:
2592:
2555:
2530:
2504:
2467:
2429:
2401:
2374:
2354:
2327:
2316:{\displaystyle g(F)}
2298:
2244:
2211:
2159:
2126:
2077:
2012:
1957:
1881:
1856:
1796:
1744:
1714:
1694:
1666:
1638:
1618:
1598:
1573:
1534:
1497:
1455:
1426:
1406:
1386:
1366:
1346:
1254:
1230:
1174:
1123:
1103:
1083:
1063:
1039:
1004:
984:
949:
921:
901:
876:
856:
831:
811:
791:
768:
731:
711:
686:
666:
557:
533:
529:when switching from
496:
388:
360:
340:
320:
275:
225:
186:
181:symmetric difference
141:
104:
72:
7388:Operations Research
7192:is before or after
4932:onto the stack if:
4211:a stack of triples
4134:Input: an instance
4100:{\displaystyle 2.2}
3877:infeasibility depth
3811:backtracking depth
2273:
1682:-regular subgraph.
1028:is in fact a tour.
31:is one of the best
7465:LKH implementation
7307:
7271:
7238:{\displaystyle 2k}
7235:
7212:
7182:
7146:
7116:
7067:
7035:
7015:
6888:
6868:
6848:
6825:
6805:
6784:
6755:
6732:
6708:
6561:
6525:
6498:
6445:
6425:
6384:
6354:
6329:
6269:
6236:
6193:
6153:
6114:
6074:
6045:
5997:
5920:
5797:
5752:
5712:
5647:
5517:
5385:
5320:
5265:
5235:
5094:
4955:
4922:
4842:
4719:
4676:
4651:
4618:
4571:
4533:
4493:
4467:
4421:
4394:
4371:
4322:
4302:
4276:
4239:
4193:
4156:
4117:
4097:
4077:
4057:
4016:
3989:
3942:Because there are
3928:
3895:
3862:
3828:
3789:{\displaystyle T'}
3786:
3758:
3738:
3706:
3678:
3642:
3565:
3536:
3413:
3368:
3328:
3270:
3143:
3088:
3063:
2986:
2863:
2823:
2800:
2693:
2660:
2616:
2578:
2536:
2516:
2490:
2453:
2407:
2387:
2360:
2340:
2313:
2284:
2247:
2230:
2197:
2145:
2112:
2063:
1993:
1943:
1862:
1842:
1782:
1723:
1700:
1672:
1652:
1624:
1604:
1587:{\displaystyle T'}
1584:
1559:
1520:
1483:
1440:{\displaystyle T'}
1437:
1422:as there are from
1412:
1392:
1372:
1352:
1332:
1236:
1216:
1160:
1109:
1089:
1069:
1045:
1018:
990:
970:
935:
907:
890:{\displaystyle T'}
887:
862:
845:{\displaystyle T'}
842:
817:
797:
780:{\displaystyle 2k}
777:
754:
717:
700:{\displaystyle T'}
697:
672:
652:
639:
603:
539:
519:
478:
464:
427:
374:{\displaystyle T'}
371:
346:
326:
306:
293:
261:
248:
211:
169:
127:
90:
7038:{\displaystyle k}
6891:{\displaystyle T}
6871:{\displaystyle k}
6851:{\displaystyle T}
6828:{\displaystyle T}
6808:{\displaystyle 2}
6758:{\displaystyle n}
6735:{\displaystyle G}
6448:{\displaystyle T}
6357:{\displaystyle T}
6208:pop all elements
5268:{\displaystyle i}
4679:{\displaystyle i}
4397:{\displaystyle F}
4325:{\displaystyle g}
4120:{\displaystyle n}
4080:{\displaystyle 2}
3761:{\displaystyle T}
3681:{\displaystyle F}
3091:{\displaystyle i}
2826:{\displaystyle i}
2539:{\displaystyle g}
2410:{\displaystyle F}
2363:{\displaystyle F}
2294:is then the gain
2073:, one may define
1865:{\displaystyle k}
1703:{\displaystyle T}
1675:{\displaystyle 2}
1627:{\displaystyle F}
1607:{\displaystyle G}
1530:that may satisfy
1486:{\displaystyle G}
1415:{\displaystyle T}
1395:{\displaystyle 4}
1375:{\displaystyle 2}
1355:{\displaystyle 0}
1239:{\displaystyle 2}
1112:{\displaystyle T}
1092:{\displaystyle T}
1072:{\displaystyle T}
1059:(with respect to
1048:{\displaystyle G}
993:{\displaystyle F}
910:{\displaystyle T}
865:{\displaystyle k}
820:{\displaystyle T}
800:{\displaystyle k}
720:{\displaystyle k}
675:{\displaystyle T}
619:
588:
542:{\displaystyle T}
443:
406:
349:{\displaystyle T}
329:{\displaystyle F}
278:
228:
45:Hamiltonian cycle
7512:
7454:
7444:
7434:
7424:
7403:
7384:Kernighan, B. W.
7371:
7370:
7350:
7344:
7343:
7331:
7316:
7314:
7313:
7308:
7306:
7305:
7280:
7278:
7277:
7272:
7270:
7269:
7244:
7242:
7241:
7236:
7221:
7219:
7218:
7213:
7211:
7210:
7191:
7189:
7188:
7183:
7181:
7180:
7155:
7153:
7152:
7147:
7145:
7144:
7125:
7123:
7122:
7117:
7115:
7114:
7096:
7095:
7076:
7074:
7073:
7068:
7044:
7042:
7041:
7036:
7024:
7022:
7021:
7016:
7014:
7013:
7004:
7003:
6985:
6984:
6957:
6956:
6947:
6946:
6916:
6911:
6910:
6897:
6895:
6894:
6889:
6877:
6875:
6874:
6869:
6858:. After picking
6857:
6855:
6854:
6849:
6834:
6832:
6831:
6826:
6814:
6812:
6811:
6806:
6793:
6791:
6790:
6785:
6764:
6762:
6761:
6756:
6741:
6739:
6738:
6733:
6717:
6715:
6714:
6709:
6704:
6703:
6694:
6693:
6672:
6671:
6653:
6652:
6631:
6630:
6621:
6620:
6608:
6607:
6598:
6597:
6585:
6570:
6568:
6567:
6562:
6560:
6559:
6534:
6532:
6531:
6526:
6524:
6523:
6507:
6505:
6504:
6499:
6494:
6454:
6452:
6451:
6446:
6434:
6432:
6431:
6426:
6424:
6416:
6393:
6391:
6390:
6385:
6383:
6382:
6363:
6361:
6360:
6355:
6338:
6336:
6335:
6330:
6322:
6321:
6278:
6276:
6275:
6270:
6268:
6267:
6245:
6243:
6242:
6237:
6202:
6200:
6199:
6194:
6192:
6191:
6162:
6160:
6159:
6154:
6149:
6123:
6121:
6120:
6115:
6107:
6106:
6083:
6081:
6080:
6075:
6054:
6052:
6051:
6046:
6006:
6004:
6003:
5998:
5996:
5995:
5983:
5982:
5943:
5942:
5929:
5927:
5926:
5921:
5916:
5915:
5906:
5905:
5881:
5880:
5871:
5870:
5858:
5857:
5848:
5847:
5823:
5822:
5806:
5804:
5803:
5798:
5790:
5789:
5761:
5759:
5758:
5753:
5742:
5721:
5719:
5718:
5713:
5708:
5707:
5698:
5697:
5673:
5672:
5656:
5654:
5653:
5648:
5643:
5642:
5633:
5632:
5620:
5619:
5610:
5609:
5585:
5584:
5575:
5574:
5562:
5561:
5552:
5551:
5526:
5524:
5523:
5518:
5513:
5512:
5503:
5502:
5490:
5489:
5480:
5479:
5455:
5454:
5445:
5444:
5432:
5431:
5422:
5421:
5409:
5394:
5392:
5391:
5386:
5384:
5383:
5368:
5367:
5358:
5357:
5329:
5327:
5326:
5321:
5316:
5315:
5306:
5305:
5274:
5272:
5271:
5266:
5244:
5242:
5241:
5236:
5231:
5230:
5212:
5211:
5199:
5198:
5189:
5188:
5164:
5163:
5154:
5153:
5141:
5140:
5131:
5130:
5118:
5103:
5101:
5100:
5095:
5087:
5086:
5074:
5073:
5064:
5063:
5039:
5038:
5029:
5028:
5016:
5015:
5006:
5005:
4984:
4983:
4964:
4962:
4961:
4956:
4954:
4953:
4931:
4929:
4928:
4923:
4921:
4920:
4908:
4907:
4868:
4867:
4851:
4849:
4848:
4843:
4838:
4837:
4828:
4827:
4803:
4802:
4793:
4792:
4780:
4779:
4770:
4769:
4745:
4744:
4728:
4726:
4725:
4720:
4709:
4685:
4683:
4682:
4677:
4660:
4658:
4657:
4652:
4644:
4643:
4627:
4625:
4624:
4619:
4580:
4578:
4577:
4572:
4542:
4540:
4539:
4534:
4523:
4502:
4500:
4499:
4494:
4476:
4474:
4473:
4468:
4460:
4459:
4430:
4428:
4427:
4422:
4420:
4419:
4403:
4401:
4400:
4395:
4380:
4378:
4377:
4372:
4364:
4363:
4351:
4350:
4331:
4329:
4328:
4323:
4311:
4309:
4308:
4303:
4285:
4283:
4282:
4277:
4266:
4248:
4246:
4245:
4240:
4202:
4200:
4199:
4194:
4183:
4165:
4163:
4162:
4157:
4126:
4124:
4123:
4118:
4106:
4104:
4103:
4098:
4086:
4084:
4083:
4078:
4067:(standard value
4066:
4064:
4063:
4058:
4050:
4045:
4044:
4025:
4023:
4022:
4017:
4015:
4014:
3998:
3996:
3995:
3990:
3985:
3984:
3977:
3972:
3971:
3937:
3935:
3934:
3929:
3921:
3920:
3904:
3902:
3901:
3896:
3894:
3893:
3871:
3869:
3868:
3863:
3855:
3854:
3837:
3835:
3834:
3829:
3827:
3826:
3795:
3793:
3792:
3787:
3785:
3767:
3765:
3764:
3759:
3747:
3745:
3744:
3739:
3715:
3713:
3712:
3707:
3702:
3687:
3685:
3684:
3679:
3651:
3649:
3648:
3643:
3641:
3640:
3628:
3627:
3588:
3587:
3574:
3572:
3571:
3566:
3545:
3543:
3542:
3537:
3532:
3531:
3522:
3521:
3497:
3496:
3487:
3486:
3474:
3473:
3464:
3463:
3439:
3438:
3422:
3420:
3419:
3414:
3406:
3405:
3377:
3375:
3374:
3369:
3358:
3337:
3335:
3334:
3329:
3318:
3317:
3308:
3307:
3279:
3277:
3276:
3271:
3266:
3265:
3256:
3255:
3243:
3242:
3233:
3232:
3208:
3207:
3198:
3197:
3185:
3184:
3175:
3174:
3152:
3150:
3149:
3144:
3139:
3138:
3129:
3128:
3097:
3095:
3094:
3089:
3072:
3070:
3069:
3064:
3062:
3061:
3049:
3048:
3009:
3008:
2995:
2993:
2992:
2987:
2982:
2981:
2972:
2971:
2947:
2946:
2937:
2936:
2924:
2923:
2914:
2913:
2889:
2888:
2872:
2870:
2869:
2864:
2853:
2832:
2830:
2829:
2824:
2809:
2807:
2806:
2801:
2796:
2795:
2786:
2785:
2761:
2760:
2751:
2750:
2738:
2737:
2728:
2727:
2702:
2700:
2699:
2694:
2686:
2685:
2669:
2667:
2666:
2661:
2625:
2623:
2622:
2617:
2587:
2585:
2584:
2579:
2568:
2545:
2543:
2542:
2537:
2525:
2523:
2522:
2517:
2499:
2497:
2496:
2491:
2480:
2462:
2460:
2459:
2454:
2416:
2414:
2413:
2408:
2396:
2394:
2393:
2388:
2386:
2385:
2369:
2367:
2366:
2361:
2349:
2347:
2346:
2341:
2339:
2338:
2322:
2320:
2319:
2314:
2293:
2291:
2290:
2285:
2283:
2282:
2272:
2261:
2239:
2237:
2236:
2231:
2223:
2222:
2206:
2204:
2203:
2198:
2193:
2192:
2171:
2170:
2154:
2152:
2151:
2146:
2138:
2137:
2121:
2119:
2118:
2113:
2108:
2107:
2089:
2088:
2072:
2070:
2069:
2064:
2062:
2061:
2041:
2040:
2030:
2029:
2002:
2000:
1999:
1994:
1952:
1950:
1949:
1944:
1936:
1935:
1934:
1933:
1903:
1898:
1871:
1869:
1868:
1863:
1851:
1849:
1848:
1843:
1835:
1834:
1824:
1813:
1791:
1789:
1788:
1783:
1781:
1780:
1756:
1755:
1732:
1730:
1729:
1724:
1709:
1707:
1706:
1701:
1681:
1679:
1678:
1673:
1661:
1659:
1658:
1653:
1648:
1633:
1631:
1630:
1625:
1613:
1611:
1610:
1605:
1593:
1591:
1590:
1585:
1583:
1568:
1566:
1565:
1560:
1558:
1550:
1529:
1527:
1526:
1521:
1510:
1492:
1490:
1489:
1484:
1479:
1471:
1446:
1444:
1443:
1438:
1436:
1421:
1419:
1418:
1413:
1401:
1399:
1398:
1393:
1381:
1379:
1378:
1373:
1361:
1359:
1358:
1353:
1341:
1339:
1338:
1333:
1331:
1330:
1324:
1316:
1296:
1291:
1290:
1278:
1270:
1245:
1243:
1242:
1237:
1225:
1223:
1222:
1217:
1215:
1214:
1208:
1188:
1183:
1182:
1169:
1167:
1166:
1161:
1159:
1158:
1137:
1132:
1131:
1118:
1116:
1115:
1110:
1098:
1096:
1095:
1090:
1078:
1076:
1075:
1070:
1054:
1052:
1051:
1046:
1027:
1025:
1024:
1019:
1014:
999:
997:
996:
991:
979:
977:
976:
971:
944:
942:
941:
936:
931:
916:
914:
913:
908:
896:
894:
893:
888:
886:
871:
869:
868:
863:
851:
849:
848:
843:
841:
826:
824:
823:
818:
806:
804:
803:
798:
786:
784:
783:
778:
763:
761:
760:
755:
744:
726:
724:
723:
718:
706:
704:
703:
698:
696:
681:
679:
678:
673:
661:
659:
658:
653:
638:
637:
602:
581:
573:
548:
546:
545:
540:
528:
526:
525:
520:
509:
487:
485:
484:
479:
463:
426:
380:
378:
377:
372:
370:
355:
353:
352:
347:
335:
333:
332:
327:
315:
313:
312:
307:
292:
270:
268:
267:
262:
247:
246:
220:
218:
217:
212:
210:
202:
178:
176:
175:
170:
159:
151:
136:
134:
133:
128:
117:
99:
97:
96:
91:
7520:
7519:
7515:
7514:
7513:
7511:
7510:
7509:
7480:
7479:
7461:
7442:
7437:
7422:10.1.1.180.1798
7406:
7378:
7375:
7374:
7367:10.1137/0221030
7352:
7351:
7347:
7333:
7332:
7328:
7323:
7288:
7283:
7282:
7252:
7247:
7246:
7224:
7223:
7199:
7194:
7193:
7163:
7158:
7157:
7133:
7128:
7127:
7097:
7084:
7079:
7078:
7047:
7046:
7027:
7026:
6986:
6967:
6948:
6938:
6900:
6899:
6880:
6879:
6860:
6859:
6840:
6839:
6817:
6816:
6797:
6796:
6767:
6766:
6747:
6746:
6724:
6723:
6695:
6676:
6654:
6641:
6622:
6612:
6599:
6589:
6573:
6572:
6542:
6537:
6536:
6515:
6510:
6509:
6482:
6481:
6478:
6437:
6436:
6417:
6404:
6403:
6400:
6374:
6369:
6368:
6346:
6345:
6313:
6308:
6307:
6259:
6248:
6247:
6210:
6209:
6183:
6172:
6171:
6131:
6130:
6098:
6093:
6092:
6060:
6059:
6019:
6018:
6007:onto the stack.
5974:
5932:
5931:
5907:
5891:
5872:
5862:
5849:
5839:
5814:
5809:
5808:
5781:
5764:
5763:
5727:
5726:
5699:
5689:
5664:
5659:
5658:
5634:
5624:
5611:
5595:
5576:
5566:
5553:
5543:
5529:
5528:
5504:
5494:
5481:
5465:
5446:
5436:
5423:
5413:
5397:
5396:
5375:
5359:
5349:
5332:
5331:
5307:
5297:
5280:
5279:
5257:
5256:
5222:
5203:
5190:
5174:
5155:
5145:
5132:
5122:
5106:
5105:
5078:
5065:
5049:
5030:
5020:
5007:
4997:
4975:
4967:
4966:
4945:
4934:
4933:
4899:
4857:
4856:
4829:
4813:
4794:
4784:
4771:
4761:
4736:
4731:
4730:
4694:
4693:
4668:
4667:
4635:
4630:
4629:
4592:
4591:
4581:onto the stack.
4545:
4544:
4508:
4507:
4479:
4478:
4451:
4446:
4445:
4411:
4406:
4405:
4386:
4385:
4355:
4342:
4337:
4336:
4314:
4313:
4288:
4287:
4251:
4250:
4213:
4212:
4168:
4167:
4136:
4135:
4109:
4108:
4089:
4088:
4069:
4068:
4036:
4028:
4027:
4006:
4001:
4000:
3963:
3955:
3944:
3943:
3912:
3907:
3906:
3885:
3880:
3879:
3846:
3841:
3840:
3818:
3813:
3812:
3803:
3778:
3773:
3772:
3750:
3749:
3721:
3720:
3690:
3689:
3670:
3669:
3652:onto the stack.
3619:
3577:
3576:
3548:
3547:
3523:
3507:
3488:
3478:
3465:
3455:
3430:
3425:
3424:
3397:
3380:
3379:
3343:
3342:
3309:
3299:
3282:
3281:
3257:
3247:
3234:
3218:
3199:
3189:
3176:
3166:
3158:
3157:
3130:
3120:
3103:
3102:
3080:
3079:
3073:onto the stack.
3040:
2998:
2997:
2973:
2957:
2938:
2928:
2915:
2905:
2880:
2875:
2874:
2838:
2837:
2815:
2814:
2787:
2771:
2752:
2742:
2729:
2719:
2705:
2704:
2677:
2672:
2671:
2634:
2633:
2626:onto the stack.
2590:
2589:
2553:
2552:
2528:
2527:
2502:
2501:
2465:
2464:
2427:
2426:
2399:
2398:
2377:
2372:
2371:
2352:
2351:
2330:
2325:
2324:
2296:
2295:
2274:
2242:
2241:
2214:
2209:
2208:
2184:
2162:
2157:
2156:
2129:
2124:
2123:
2099:
2080:
2075:
2074:
2047:
2032:
2021:
2010:
2009:
1955:
1954:
1905:
1879:
1878:
1854:
1853:
1826:
1794:
1793:
1766:
1747:
1742:
1741:
1712:
1711:
1692:
1691:
1688:
1664:
1663:
1636:
1635:
1616:
1615:
1596:
1595:
1576:
1571:
1570:
1551:
1532:
1531:
1495:
1494:
1472:
1453:
1452:
1429:
1424:
1423:
1404:
1403:
1384:
1383:
1364:
1363:
1344:
1343:
1317:
1271:
1252:
1251:
1250:, the subgraph
1228:
1227:
1201:
1172:
1171:
1121:
1120:
1101:
1100:
1081:
1080:
1061:
1060:
1037:
1036:
1002:
1001:
982:
981:
947:
946:
919:
918:
899:
898:
879:
874:
873:
854:
853:
834:
829:
828:
809:
808:
789:
788:
766:
765:
729:
728:
709:
708:
689:
684:
683:
664:
663:
630:
574:
555:
554:
531:
530:
494:
493:
386:
385:
363:
358:
357:
338:
337:
318:
317:
273:
272:
239:
223:
222:
203:
184:
183:
144:
139:
138:
102:
101:
70:
69:
66:
21:
12:
11:
5:
7518:
7516:
7508:
7507:
7502:
7497:
7492:
7482:
7481:
7478:
7477:
7472:
7467:
7460:
7459:External links
7457:
7456:
7455:
7435:
7415:(1): 106–130.
7404:
7394:(2): 498–516.
7373:
7372:
7361:(3): 450–465.
7345:
7325:
7324:
7322:
7319:
7304:
7301:
7298:
7295:
7291:
7268:
7265:
7262:
7259:
7255:
7234:
7231:
7209:
7206:
7202:
7179:
7176:
7173:
7170:
7166:
7143:
7140:
7136:
7113:
7110:
7107:
7104:
7100:
7094:
7091:
7087:
7066:
7063:
7060:
7057:
7054:
7034:
7012:
7007:
7002:
6999:
6996:
6993:
6989:
6983:
6980:
6977:
6974:
6970:
6966:
6963:
6960:
6955:
6951:
6945:
6941:
6937:
6934:
6931:
6928:
6925:
6922:
6919:
6915:
6909:
6887:
6867:
6847:
6824:
6804:
6783:
6780:
6777:
6774:
6754:
6731:
6707:
6702:
6698:
6692:
6689:
6686:
6683:
6679:
6675:
6670:
6667:
6664:
6661:
6657:
6651:
6648:
6644:
6640:
6637:
6634:
6629:
6625:
6619:
6615:
6611:
6606:
6602:
6596:
6592:
6588:
6584:
6580:
6558:
6555:
6552:
6549:
6545:
6522:
6518:
6497:
6493:
6489:
6477:
6474:
6444:
6423:
6420:
6415:
6411:
6399:
6396:
6381:
6377:
6365:
6364:
6353:
6340:
6328:
6325:
6320:
6316:
6302:
6301:
6300:
6295:
6294:
6293:
6288:
6287:
6286:
6281:
6280:
6279:
6266:
6262:
6258:
6255:
6235:
6232:
6229:
6226:
6223:
6220:
6217:
6190:
6186:
6182:
6179:
6166:
6165:
6164:
6152:
6148:
6144:
6141:
6138:
6113:
6110:
6105:
6101:
6073:
6070:
6067:
6044:
6041:
6038:
6035:
6032:
6029:
6026:
6015:
6010:
6009:
6008:
5994:
5989:
5986:
5981:
5977:
5973:
5970:
5967:
5964:
5961:
5958:
5955:
5952:
5949:
5946:
5941:
5919:
5914:
5910:
5904:
5901:
5898:
5894:
5890:
5887:
5884:
5879:
5875:
5869:
5865:
5861:
5856:
5852:
5846:
5842:
5838:
5835:
5832:
5829:
5826:
5821:
5817:
5796:
5793:
5788:
5784:
5780:
5777:
5774:
5771:
5751:
5748:
5745:
5741:
5737:
5734:
5723:
5711:
5706:
5702:
5696:
5692:
5688:
5685:
5682:
5679:
5676:
5671:
5667:
5646:
5641:
5637:
5631:
5627:
5623:
5618:
5614:
5608:
5605:
5602:
5598:
5594:
5591:
5588:
5583:
5579:
5573:
5569:
5565:
5560:
5556:
5550:
5546:
5542:
5539:
5536:
5516:
5511:
5507:
5501:
5497:
5493:
5488:
5484:
5478:
5475:
5472:
5468:
5464:
5461:
5458:
5453:
5449:
5443:
5439:
5435:
5430:
5426:
5420:
5416:
5412:
5408:
5404:
5382:
5378:
5374:
5371:
5366:
5362:
5356:
5352:
5348:
5345:
5342:
5339:
5319:
5314:
5310:
5304:
5300:
5296:
5293:
5290:
5287:
5264:
5250:
5249:
5248:
5247:
5246:
5234:
5229:
5225:
5221:
5218:
5215:
5210:
5206:
5202:
5197:
5193:
5187:
5184:
5181:
5177:
5173:
5170:
5167:
5162:
5158:
5152:
5148:
5144:
5139:
5135:
5129:
5125:
5121:
5117:
5113:
5093:
5090:
5085:
5081:
5077:
5072:
5068:
5062:
5059:
5056:
5052:
5048:
5045:
5042:
5037:
5033:
5027:
5023:
5019:
5014:
5010:
5004:
5000:
4996:
4993:
4990:
4987:
4982:
4978:
4974:
4952:
4948:
4944:
4941:
4919:
4914:
4911:
4906:
4902:
4898:
4895:
4892:
4889:
4886:
4883:
4880:
4877:
4874:
4871:
4866:
4841:
4836:
4832:
4826:
4823:
4820:
4816:
4812:
4809:
4806:
4801:
4797:
4791:
4787:
4783:
4778:
4774:
4768:
4764:
4760:
4757:
4754:
4751:
4748:
4743:
4739:
4718:
4715:
4712:
4708:
4704:
4701:
4675:
4662:
4650:
4647:
4642:
4638:
4617:
4614:
4611:
4608:
4605:
4602:
4599:
4582:
4570:
4567:
4564:
4561:
4558:
4555:
4552:
4532:
4529:
4526:
4522:
4518:
4515:
4504:
4492:
4489:
4486:
4466:
4463:
4458:
4454:
4437:
4434:
4433:
4432:
4418:
4414:
4393:
4382:
4370:
4367:
4362:
4358:
4354:
4349:
4345:
4333:
4321:
4301:
4298:
4295:
4275:
4272:
4269:
4265:
4261:
4258:
4238:
4235:
4232:
4229:
4226:
4223:
4220:
4206:
4203:
4192:
4189:
4186:
4182:
4178:
4175:
4155:
4152:
4149:
4146:
4143:
4116:
4096:
4076:
4056:
4053:
4049:
4043:
4039:
4035:
4013:
4009:
3988:
3983:
3980:
3976:
3970:
3966:
3962:
3958:
3954:
3951:
3940:
3939:
3927:
3924:
3919:
3915:
3892:
3888:
3873:
3861:
3858:
3853:
3849:
3825:
3821:
3802:
3799:
3798:
3797:
3784:
3781:
3769:
3757:
3737:
3734:
3731:
3728:
3717:
3705:
3701:
3697:
3677:
3661:
3660:
3657:
3656:
3655:
3654:
3653:
3639:
3634:
3631:
3626:
3622:
3618:
3615:
3612:
3609:
3606:
3603:
3600:
3597:
3594:
3591:
3586:
3564:
3561:
3558:
3555:
3546:(there may be
3535:
3530:
3526:
3520:
3517:
3514:
3510:
3506:
3503:
3500:
3495:
3491:
3485:
3481:
3477:
3472:
3468:
3462:
3458:
3454:
3451:
3448:
3445:
3442:
3437:
3433:
3412:
3409:
3404:
3400:
3396:
3393:
3390:
3387:
3367:
3364:
3361:
3357:
3353:
3350:
3339:
3327:
3324:
3321:
3316:
3312:
3306:
3302:
3298:
3295:
3292:
3289:
3269:
3264:
3260:
3254:
3250:
3246:
3241:
3237:
3231:
3228:
3225:
3221:
3217:
3214:
3211:
3206:
3202:
3196:
3192:
3188:
3183:
3179:
3173:
3169:
3165:
3142:
3137:
3133:
3127:
3123:
3119:
3116:
3113:
3110:
3087:
3076:
3075:
3074:
3060:
3055:
3052:
3047:
3043:
3039:
3036:
3033:
3030:
3027:
3024:
3021:
3018:
3015:
3012:
3007:
2985:
2980:
2976:
2970:
2967:
2964:
2960:
2956:
2953:
2950:
2945:
2941:
2935:
2931:
2927:
2922:
2918:
2912:
2908:
2904:
2901:
2898:
2895:
2892:
2887:
2883:
2862:
2859:
2856:
2852:
2848:
2845:
2833:is even then:
2822:
2811:
2799:
2794:
2790:
2784:
2781:
2778:
2774:
2770:
2767:
2764:
2759:
2755:
2749:
2745:
2741:
2736:
2732:
2726:
2722:
2718:
2715:
2712:
2692:
2689:
2684:
2680:
2659:
2656:
2653:
2650:
2647:
2644:
2641:
2627:
2615:
2612:
2609:
2606:
2603:
2600:
2597:
2577:
2574:
2571:
2567:
2563:
2560:
2548:
2547:
2535:
2515:
2512:
2509:
2489:
2486:
2483:
2479:
2475:
2472:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2406:
2384:
2380:
2359:
2337:
2333:
2312:
2309:
2306:
2303:
2281:
2277:
2271:
2268:
2265:
2260:
2257:
2254:
2250:
2229:
2226:
2221:
2217:
2196:
2191:
2187:
2183:
2180:
2177:
2174:
2169:
2165:
2144:
2141:
2136:
2132:
2111:
2106:
2102:
2098:
2095:
2092:
2087:
2083:
2060:
2057:
2054:
2050:
2045:
2039:
2035:
2028:
2024:
2020:
2017:
2006:
2005:
1992:
1989:
1986:
1983:
1980:
1977:
1974:
1971:
1968:
1965:
1962:
1942:
1939:
1932:
1928:
1924:
1921:
1918:
1915:
1912:
1908:
1902:
1897:
1894:
1891:
1887:
1861:
1841:
1838:
1833:
1829:
1823:
1820:
1817:
1812:
1809:
1806:
1802:
1779:
1776:
1773:
1769:
1765:
1762:
1759:
1754:
1750:
1722:
1719:
1699:
1687:
1684:
1671:
1651:
1647:
1643:
1623:
1603:
1582:
1579:
1569:for some tour
1557:
1554:
1549:
1545:
1542:
1539:
1519:
1516:
1513:
1509:
1505:
1502:
1482:
1478:
1475:
1470:
1466:
1463:
1460:
1435:
1432:
1411:
1391:
1371:
1351:
1329:
1323:
1320:
1315:
1311:
1308:
1305:
1302:
1299:
1295:
1289:
1284:
1281:
1277:
1274:
1269:
1265:
1262:
1259:
1235:
1213:
1207:
1204:
1200:
1197:
1194:
1191:
1187:
1181:
1157:
1152:
1149:
1146:
1143:
1140:
1136:
1130:
1108:
1088:
1068:
1044:
1017:
1013:
1009:
989:
969:
966:
963:
960:
957:
954:
934:
930:
926:
906:
885:
882:
861:
852:, and another
840:
837:
816:
796:
776:
773:
753:
750:
747:
743:
739:
736:
716:
695:
692:
671:
651:
648:
645:
642:
636:
633:
629:
626:
622:
618:
615:
612:
609:
606:
601:
598:
595:
591:
587:
584:
580:
577:
572:
568:
565:
562:
551:
550:
538:
518:
515:
512:
508:
504:
501:
476:
473:
470:
467:
462:
459:
456:
453:
450:
446:
442:
439:
436:
433:
430:
425:
422:
419:
416:
413:
409:
405:
402:
399:
396:
393:
369:
366:
345:
325:
305:
302:
299:
296:
291:
288:
285:
281:
260:
257:
254:
251:
245:
242:
238:
235:
231:
209:
206:
201:
197:
194:
191:
179:such that the
168:
165:
162:
158:
154:
150:
147:
126:
123:
120:
116:
112:
109:
89:
86:
83:
80:
77:
65:
62:
13:
10:
9:
6:
4:
3:
2:
7517:
7506:
7503:
7501:
7498:
7496:
7493:
7491:
7488:
7487:
7485:
7476:
7473:
7471:
7468:
7466:
7463:
7462:
7458:
7452:
7448:
7447:J. K. Lenstra
7441:
7436:
7432:
7428:
7423:
7418:
7414:
7410:
7405:
7401:
7397:
7393:
7389:
7385:
7381:
7377:
7376:
7368:
7364:
7360:
7356:
7349:
7346:
7341:
7337:
7330:
7327:
7320:
7318:
7302:
7299:
7296:
7293:
7289:
7266:
7263:
7260:
7257:
7253:
7232:
7229:
7207:
7204:
7200:
7177:
7174:
7171:
7168:
7164:
7141:
7138:
7134:
7111:
7108:
7105:
7102:
7098:
7092:
7089:
7085:
7061:
7058:
7055:
7032:
7000:
6997:
6994:
6991:
6987:
6981:
6978:
6975:
6972:
6968:
6964:
6961:
6958:
6953:
6949:
6943:
6939:
6929:
6926:
6920:
6885:
6865:
6845:
6836:
6822:
6802:
6778:
6772:
6752:
6743:
6729:
6721:
6700:
6696:
6690:
6687:
6684:
6681:
6677:
6673:
6668:
6665:
6662:
6659:
6655:
6649:
6646:
6642:
6638:
6635:
6632:
6627:
6623:
6617:
6613:
6609:
6604:
6600:
6594:
6590:
6578:
6556:
6553:
6550:
6547:
6543:
6520:
6516:
6495:
6487:
6475:
6473:
6470:
6465:
6461:
6458:
6442:
6421:
6418:
6409:
6397:
6395:
6379:
6375:
6351:
6344:
6341:
6326:
6323:
6318:
6314:
6306:
6303:
6299:
6296:
6292:
6289:
6285:
6282:
6264:
6260:
6256:
6253:
6230:
6227:
6224:
6221:
6218:
6207:
6206:
6205:
6188:
6184:
6180:
6177:
6170:
6167:
6150:
6142:
6139:
6136:
6128:
6127:
6126:
6111:
6108:
6103:
6099:
6091:
6088:
6087:
6086:
6071:
6068:
6065:
6058:
6039:
6036:
6033:
6030:
6027:
6016:
6014:
6011:
5984:
5979:
5975:
5968:
5965:
5962:
5959:
5956:
5953:
5950:
5947:
5944:
5912:
5908:
5902:
5899:
5896:
5892:
5888:
5885:
5882:
5877:
5873:
5867:
5863:
5859:
5854:
5850:
5844:
5840:
5833:
5830:
5827:
5824:
5819:
5815:
5791:
5786:
5782:
5775:
5772:
5769:
5746:
5735:
5732:
5724:
5704:
5700:
5694:
5690:
5683:
5680:
5677:
5674:
5669:
5665:
5639:
5635:
5629:
5625:
5621:
5616:
5612:
5606:
5603:
5600:
5596:
5592:
5589:
5586:
5581:
5577:
5571:
5567:
5563:
5558:
5554:
5548:
5544:
5537:
5534:
5509:
5505:
5499:
5495:
5491:
5486:
5482:
5476:
5473:
5470:
5466:
5462:
5459:
5456:
5451:
5447:
5441:
5437:
5433:
5428:
5424:
5418:
5414:
5402:
5380:
5376:
5372:
5364:
5360:
5354:
5350:
5343:
5340:
5337:
5312:
5308:
5302:
5298:
5291:
5288:
5285:
5277:
5276:
5262:
5254:
5251:
5227:
5223:
5219:
5216:
5213:
5208:
5204:
5200:
5195:
5191:
5185:
5182:
5179:
5175:
5171:
5168:
5165:
5160:
5156:
5150:
5146:
5142:
5137:
5133:
5127:
5123:
5111:
5088:
5083:
5079:
5075:
5070:
5066:
5060:
5057:
5054:
5050:
5046:
5043:
5040:
5035:
5031:
5025:
5021:
5017:
5012:
5008:
5002:
4998:
4991:
4988:
4985:
4980:
4976:
4972:
4950:
4946:
4942:
4939:
4909:
4904:
4900:
4893:
4890:
4887:
4884:
4881:
4878:
4875:
4872:
4869:
4854:
4853:
4834:
4830:
4824:
4821:
4818:
4814:
4810:
4807:
4804:
4799:
4795:
4789:
4785:
4781:
4776:
4772:
4766:
4762:
4752:
4749:
4746:
4741:
4737:
4713:
4702:
4699:
4691:
4690:
4689:
4673:
4666:
4663:
4648:
4645:
4640:
4636:
4612:
4609:
4606:
4603:
4600:
4589:
4588:
4586:
4583:
4565:
4562:
4559:
4556:
4553:
4527:
4516:
4513:
4505:
4487:
4484:
4464:
4461:
4456:
4452:
4443:
4442:
4441:
4438:
4435:
4416:
4412:
4391:
4384:the best set
4383:
4368:
4365:
4360:
4356:
4352:
4347:
4343:
4335:the sequence
4334:
4319:
4299:
4296:
4293:
4286:is a vertex,
4270:
4259:
4256:
4233:
4230:
4227:
4224:
4221:
4210:
4209:
4207:
4204:
4187:
4176:
4173:
4150:
4147:
4144:
4133:
4132:
4131:
4128:
4114:
4094:
4074:
4051:
4047:
4041:
4037:
4011:
4007:
3978:
3974:
3968:
3964:
3956:
3949:
3925:
3922:
3917:
3913:
3890:
3886:
3878:
3874:
3859:
3856:
3851:
3847:
3838:
3823:
3819:
3808:
3807:
3806:
3800:
3782:
3779:
3770:
3755:
3735:
3732:
3729:
3726:
3718:
3703:
3695:
3675:
3667:
3666:
3665:
3658:
3629:
3624:
3620:
3613:
3610:
3607:
3604:
3601:
3598:
3595:
3592:
3589:
3559:
3553:
3528:
3524:
3518:
3515:
3512:
3508:
3504:
3501:
3498:
3493:
3489:
3483:
3479:
3475:
3470:
3466:
3460:
3456:
3449:
3446:
3443:
3440:
3435:
3431:
3407:
3402:
3398:
3391:
3388:
3385:
3362:
3351:
3348:
3340:
3325:
3322:
3314:
3310:
3304:
3300:
3293:
3290:
3287:
3262:
3258:
3252:
3248:
3244:
3239:
3235:
3229:
3226:
3223:
3219:
3215:
3212:
3209:
3204:
3200:
3194:
3190:
3186:
3181:
3177:
3171:
3167:
3156:
3135:
3131:
3125:
3121:
3114:
3111:
3108:
3100:
3099:
3098:is odd then:
3085:
3077:
3050:
3045:
3041:
3034:
3031:
3028:
3025:
3022:
3019:
3016:
3013:
3010:
2978:
2974:
2968:
2965:
2962:
2958:
2954:
2951:
2948:
2943:
2939:
2933:
2929:
2925:
2920:
2916:
2910:
2906:
2896:
2893:
2890:
2885:
2881:
2857:
2846:
2843:
2835:
2834:
2820:
2812:
2792:
2788:
2782:
2779:
2776:
2772:
2768:
2765:
2762:
2757:
2753:
2747:
2743:
2739:
2734:
2730:
2724:
2720:
2713:
2710:
2690:
2687:
2682:
2678:
2654:
2651:
2648:
2645:
2642:
2631:
2630:
2628:
2610:
2607:
2604:
2601:
2598:
2572:
2561:
2558:
2550:
2549:
2533:
2513:
2510:
2507:
2500:is a vertex,
2484:
2473:
2470:
2447:
2444:
2441:
2438:
2435:
2424:
2423:
2422:
2419:
2404:
2382:
2378:
2357:
2335:
2331:
2307:
2301:
2279:
2275:
2269:
2266:
2263:
2258:
2255:
2252:
2227:
2224:
2219:
2215:
2189:
2185:
2178:
2175:
2172:
2167:
2163:
2142:
2139:
2134:
2130:
2104:
2100:
2093:
2090:
2085:
2081:
2058:
2055:
2052:
2048:
2043:
2037:
2033:
2026:
2022:
2018:
2015:
2004:
1990:
1987:
1984:
1981:
1978:
1975:
1972:
1969:
1966:
1963:
1960:
1940:
1937:
1930:
1919:
1916:
1913:
1906:
1900:
1895:
1892:
1889:
1885:
1876:
1875:
1874:
1873:
1859:
1839:
1836:
1831:
1827:
1821:
1818:
1815:
1810:
1807:
1804:
1800:
1777:
1774:
1771:
1767:
1763:
1760:
1757:
1752:
1748:
1738:
1734:
1720:
1717:
1697:
1685:
1683:
1669:
1649:
1641:
1621:
1601:
1580:
1577:
1555:
1552:
1543:
1540:
1537:
1514:
1503:
1500:
1476:
1473:
1464:
1458:
1450:
1433:
1430:
1409:
1389:
1369:
1349:
1321:
1318:
1309:
1306:
1300:
1282:
1275:
1272:
1263:
1257:
1249:
1233:
1205:
1202:
1198:
1192:
1150:
1147:
1141:
1106:
1086:
1066:
1058:
1042:
1034:
1029:
1015:
1007:
987:
967:
964:
958:
952:
932:
924:
904:
883:
880:
859:
838:
835:
814:
794:
774:
771:
764:with exactly
748:
737:
734:
714:
693:
690:
669:
646:
640:
634:
631:
627:
624:
620:
616:
610:
604:
599:
596:
593:
589:
585:
578:
575:
566:
560:
536:
513:
502:
499:
491:
471:
465:
460:
454:
451:
448:
444:
440:
434:
428:
423:
420:
417:
414:
411:
407:
403:
397:
391:
384:
383:
382:
367:
364:
343:
323:
300:
294:
289:
286:
283:
279:
255:
249:
243:
240:
236:
233:
229:
207:
204:
195:
192:
189:
182:
163:
152:
148:
145:
121:
110:
107:
84:
81:
78:
63:
61:
58:
54:
50:
46:
42:
38:
34:
30:
29:Lin–Kernighan
26:
19:
7450:
7412:
7408:
7391:
7387:
7358:
7354:
7348:
7339:
7335:
7329:
7281:; as far as
7025:consists of
6837:
6744:
6479:
6468:
6466:
6462:
6456:
6401:
6366:
6342:
6304:
6297:
6290:
6283:
6203:
6168:
6124:
6089:
6084:
6056:
6012:
5252:
4687:
4664:
4584:
4439:
4129:
3941:
3876:
3810:
3804:
3662:
3154:
2420:
2007:
1877:
1739:
1736:
1735:
1689:
1451:) the graph
1056:
1030:
917:) such that
552:
489:
67:
41:local search
28:
22:
6878:edges from
6815:edges from
6398:Limitations
4208:Variables:
3078:If instead
1099:and not in
1057:alternating
897:but not in
827:but not in
7484:Categories
7321:References
6469:asymmetric
6457:sequential
5762:such that
4729:such that
3716:is a tour.
3378:such that
2873:such that
2240:; the sum
787:elements (
707:. Naively
64:Derivation
33:heuristics
7417:CiteSeerX
7380:Lin, Shen
7264:−
6998:−
6979:−
6962:…
6933:∖
6636:…
6583:△
6492:△
6414:△
6319:∗
6298:end while
6147:△
6104:∗
6069:≤
5966:−
5900:−
5886:…
5834:∪
5828:∉
5736:∈
5725:For each
5681:−
5670:∗
5604:−
5590:…
5474:−
5460:…
5407:△
5381:∗
5341:−
5275:is odd):
5183:−
5169:…
5116:△
5058:−
5044:…
4992:∪
4986:∉
4943:≤
4822:−
4808:…
4756:∖
4750:∈
4703:∈
4692:for each
4517:∈
4491:∅
4457:∗
4417:∗
4369:…
4297:≥
4260:∈
4177:⊂
4055:⌋
4034:⌊
3982:⌋
3961:⌊
3700:△
3611:−
3516:−
3502:…
3450:∪
3444:∉
3352:∈
3341:For each
3291:−
3227:−
3213:…
2966:−
2952:…
2900:∖
2894:∈
2847:∈
2836:For each
2780:−
2766:…
2562:∈
2511:≥
2474:∈
2267:−
2249:∑
2225:∉
2176:−
2140:∈
2056:−
2044:…
1988:−
1979:…
1886:∑
1872:such that
1819:−
1801:∑
1775:−
1761:…
1718:≤
1646:△
1548:△
1504:⊆
1469:△
1314:△
1268:△
1031:Define a
1012:△
929:△
738:⊆
628:∈
621:∑
617:−
597:∈
590:∑
571:△
503:⊆
492:of using
458:∖
452:∈
445:∑
441:−
421:∩
415:∈
408:∑
287:∈
280:∑
237:∈
230:∑
200:△
153:⊂
111:⊂
7449:(eds.).
7077:th edge
6720:2-factor
6467:For the
6422:′
4686:is even
4506:For all
4249:, where
3783:′
2551:For all
2463:, where
1953:for all
1686:Key idea
1581:′
1556:′
1477:′
1434:′
1322:′
1276:′
1206:′
884:′
839:′
694:′
635:′
579:′
368:′
244:′
208:′
149:′
7342:: 3–26.
6169:else if
6013:End if.
5930:, push
4543:, push
2588:, push
1248:regular
7419:
6343:Return
6291:end if
6284:end if
5395:, and
4440:Repeat
3155:report
1737:Lemma.
1634:makes
1382:, and
1055:to be
553:since
488:— the
60:or 3.
7443:(PDF)
6305:until
4965:, or
4855:push
4585:While
3153:then
1033:trail
57:edges
53:3-opt
49:2-opt
6257:>
6204:then
6181:>
6129:set
6125:then
6109:>
6085:then
6017:Let
5807:and
5773:>
5657:and
5373:>
5289:>
5253:else
5104:and
4688:then
4590:Pop
4477:and
4444:Set
3875:The
3809:The
3659:Stop
3423:and
3389:>
3323:>
3112:>
2632:Pop
2155:and
1938:>
1837:>
1226:are
1170:and
965:>
490:gain
356:and
51:and
7427:doi
7413:126
7396:doi
7363:doi
6722:in
5278:If
4095:2.2
3101:If
2813:If
2207:if
2122:if
1927:mod
1740:If
1035:in
872:in
807:in
23:In
7486::
7425:.
7411:.
7392:21
7390:.
7382:;
7359:21
7357:.
7340:11
7338:.
6140::=
6090:if
6057:If
5675::=
5538::=
5330:,
4852:,
4665:If
4646::=
4488::=
4462::=
2688::=
1362:,
27:,
7433:.
7429::
7402:.
7398::
7369:.
7365::
7303:1
7300:+
7297:k
7294:2
7290:v
7267:1
7261:k
7258:2
7254:v
7233:k
7230:2
7208:k
7205:2
7201:v
7178:1
7175:+
7172:k
7169:2
7165:v
7142:k
7139:2
7135:v
7112:1
7109:+
7106:k
7103:2
7099:v
7093:k
7090:2
7086:v
7065:)
7062:1
7059:+
7056:k
7053:(
7033:k
7011:)
7006:}
7001:1
6995:k
6992:2
6988:v
6982:2
6976:k
6973:2
6969:v
6965:,
6959:,
6954:1
6950:v
6944:0
6940:v
6936:{
6930:T
6927:,
6924:)
6921:G
6918:(
6914:V
6908:(
6886:T
6866:k
6846:T
6823:T
6803:2
6782:)
6779:n
6776:(
6773:O
6753:n
6730:G
6706:}
6701:0
6697:v
6691:1
6688:+
6685:k
6682:2
6678:v
6674:,
6669:1
6666:+
6663:k
6660:2
6656:v
6650:k
6647:2
6643:v
6639:,
6633:,
6628:2
6624:v
6618:1
6614:v
6610:,
6605:1
6601:v
6595:0
6591:v
6587:{
6579:T
6557:1
6554:+
6551:k
6548:2
6544:v
6521:2
6517:p
6496:F
6488:T
6443:T
6419:T
6410:T
6380:1
6376:p
6352:T
6339:.
6327:0
6324:=
6315:g
6265:1
6261:p
6254:j
6234:)
6231:g
6228:,
6225:j
6222:,
6219:u
6216:(
6189:1
6185:p
6178:i
6151:F
6143:T
6137:T
6112:0
6100:g
6072:j
6066:i
6043:)
6040:g
6037:,
6034:j
6031:,
6028:u
6025:(
5993:)
5988:)
5985:u
5980:i
5976:v
5972:(
5969:c
5963:g
5960:,
5957:1
5954:+
5951:i
5948:,
5945:u
5940:(
5918:}
5913:i
5909:v
5903:1
5897:i
5893:v
5889:,
5883:,
5878:2
5874:v
5868:1
5864:v
5860:,
5855:1
5851:v
5845:0
5841:v
5837:{
5831:T
5825:u
5820:i
5816:v
5795:)
5792:u
5787:i
5783:v
5779:(
5776:c
5770:g
5750:)
5747:G
5744:(
5740:V
5733:u
5722:.
5710:)
5705:0
5701:v
5695:i
5691:v
5687:(
5684:c
5678:g
5666:g
5645:}
5640:0
5636:v
5630:i
5626:v
5622:,
5617:i
5613:v
5607:1
5601:i
5597:v
5593:,
5587:,
5582:2
5578:v
5572:1
5568:v
5564:,
5559:1
5555:v
5549:0
5545:v
5541:{
5535:F
5515:}
5510:0
5506:v
5500:i
5496:v
5492:,
5487:i
5483:v
5477:1
5471:i
5467:v
5463:,
5457:,
5452:2
5448:v
5442:1
5438:v
5434:,
5429:1
5425:v
5419:0
5415:v
5411:{
5403:T
5377:g
5370:)
5365:0
5361:v
5355:i
5351:v
5347:(
5344:c
5338:g
5318:)
5313:0
5309:v
5303:i
5299:v
5295:(
5292:c
5286:g
5263:i
5255:(
5233:}
5228:0
5224:v
5220:u
5217:,
5214:u
5209:i
5205:v
5201:,
5196:i
5192:v
5186:1
5180:i
5176:v
5172:,
5166:,
5161:2
5157:v
5151:1
5147:v
5143:,
5138:1
5134:v
5128:0
5124:v
5120:{
5112:T
5092:}
5089:u
5084:i
5080:v
5076:,
5071:i
5067:v
5061:1
5055:i
5051:v
5047:,
5041:,
5036:2
5032:v
5026:1
5022:v
5018:,
5013:1
5009:v
5003:0
4999:v
4995:{
4989:T
4981:0
4977:v
4973:u
4951:2
4947:p
4940:i
4918:)
4913:)
4910:u
4905:i
4901:v
4897:(
4894:c
4891:+
4888:g
4885:,
4882:1
4879:+
4876:i
4873:,
4870:u
4865:(
4840:}
4835:i
4831:v
4825:1
4819:i
4815:v
4811:,
4805:,
4800:2
4796:v
4790:1
4786:v
4782:,
4777:1
4773:v
4767:0
4763:v
4759:{
4753:T
4747:u
4742:i
4738:v
4717:)
4714:G
4711:(
4707:V
4700:u
4674:i
4661:.
4649:u
4641:i
4637:v
4616:)
4613:g
4610:,
4607:i
4604:,
4601:u
4598:(
4569:)
4566:0
4563:,
4560:0
4557:,
4554:u
4551:(
4531:)
4528:G
4525:(
4521:V
4514:u
4503:.
4485:F
4465:0
4453:g
4431:.
4413:g
4392:F
4366:,
4361:1
4357:v
4353:,
4348:0
4344:v
4320:g
4300:0
4294:i
4274:)
4271:G
4268:(
4264:V
4257:u
4237:)
4234:g
4231:,
4228:i
4225:,
4222:u
4219:(
4191:)
4188:G
4185:(
4181:E
4174:T
4154:)
4151:c
4148:,
4145:G
4142:(
4115:n
4075:2
4052:2
4048:/
4042:1
4038:p
4012:1
4008:p
3987:)
3979:2
3975:/
3969:1
3965:p
3957:n
3953:(
3950:O
3938:.
3926:2
3923:=
3918:2
3914:p
3891:2
3887:p
3872:.
3860:5
3857:=
3852:1
3848:p
3824:1
3820:p
3780:T
3756:T
3736:n
3733:2
3730:=
3727:i
3704:F
3696:T
3676:F
3638:)
3633:)
3630:u
3625:i
3621:v
3617:(
3614:c
3608:g
3605:,
3602:1
3599:+
3596:i
3593:,
3590:u
3585:(
3563:)
3560:n
3557:(
3554:O
3534:}
3529:i
3525:v
3519:1
3513:i
3509:v
3505:,
3499:,
3494:2
3490:v
3484:1
3480:v
3476:,
3471:1
3467:v
3461:0
3457:v
3453:{
3447:T
3441:u
3436:i
3432:v
3411:)
3408:u
3403:i
3399:v
3395:(
3392:c
3386:g
3366:)
3363:G
3360:(
3356:V
3349:u
3338:.
3326:0
3320:)
3315:0
3311:v
3305:i
3301:v
3297:(
3294:c
3288:g
3268:}
3263:0
3259:v
3253:i
3249:v
3245:,
3240:i
3236:v
3230:1
3224:i
3220:v
3216:,
3210:,
3205:2
3201:v
3195:1
3191:v
3187:,
3182:1
3178:v
3172:0
3168:v
3164:{
3141:)
3136:0
3132:v
3126:i
3122:v
3118:(
3115:c
3109:g
3086:i
3059:)
3054:)
3051:u
3046:i
3042:v
3038:(
3035:c
3032:+
3029:g
3026:,
3023:1
3020:+
3017:i
3014:,
3011:u
3006:(
2984:}
2979:i
2975:v
2969:1
2963:i
2959:v
2955:,
2949:,
2944:2
2940:v
2934:1
2930:v
2926:,
2921:1
2917:v
2911:0
2907:v
2903:{
2897:T
2891:u
2886:i
2882:v
2861:)
2858:G
2855:(
2851:V
2844:u
2821:i
2810:.
2798:}
2793:i
2789:v
2783:1
2777:i
2773:v
2769:,
2763:,
2758:2
2754:v
2748:1
2744:v
2740:,
2735:1
2731:v
2725:0
2721:v
2717:{
2714:=
2711:F
2691:u
2683:i
2679:v
2658:)
2655:g
2652:,
2649:i
2646:,
2643:u
2640:(
2614:)
2611:0
2608:,
2605:0
2602:,
2599:u
2596:(
2576:)
2573:G
2570:(
2566:V
2559:u
2534:g
2514:0
2508:i
2488:)
2485:G
2482:(
2478:V
2471:u
2451:)
2448:g
2445:,
2442:i
2439:,
2436:u
2433:(
2405:F
2383:0
2379:v
2358:F
2336:0
2332:v
2311:)
2308:F
2305:(
2302:g
2280:i
2276:a
2270:1
2264:n
2259:0
2256:=
2253:i
2228:T
2220:i
2216:e
2195:)
2190:i
2186:e
2182:(
2179:c
2173:=
2168:i
2164:a
2143:T
2135:i
2131:e
2110:)
2105:i
2101:e
2097:(
2094:c
2091:=
2086:i
2082:a
2059:1
2053:n
2049:e
2038:1
2034:e
2027:0
2023:e
2019:=
2016:F
2003:.
1991:1
1985:n
1982:,
1976:,
1973:1
1970:,
1967:0
1964:=
1961:r
1941:0
1931:n
1923:)
1920:i
1917:+
1914:k
1911:(
1907:a
1901:r
1896:0
1893:=
1890:i
1860:k
1840:0
1832:i
1828:a
1822:1
1816:n
1811:0
1808:=
1805:i
1778:1
1772:n
1768:a
1764:,
1758:,
1753:0
1749:a
1721:0
1698:T
1670:2
1650:F
1642:T
1622:F
1602:G
1578:T
1553:T
1544:T
1541:=
1538:F
1518:)
1515:G
1512:(
1508:E
1501:F
1481:]
1474:T
1465:T
1462:[
1459:G
1431:T
1410:T
1390:4
1370:2
1350:0
1328:)
1319:T
1310:T
1307:,
1304:)
1301:G
1298:(
1294:V
1288:(
1283:=
1280:]
1273:T
1264:T
1261:[
1258:G
1246:-
1234:2
1212:)
1203:T
1199:,
1196:)
1193:G
1190:(
1186:V
1180:(
1156:)
1151:T
1148:,
1145:)
1142:G
1139:(
1135:V
1129:(
1107:T
1087:T
1067:T
1043:G
1016:F
1008:T
988:F
968:0
962:)
959:F
956:(
953:g
933:F
925:T
905:T
881:T
860:k
836:T
815:T
795:k
775:k
772:2
752:)
749:G
746:(
742:E
735:F
715:k
691:T
670:T
650:)
647:e
644:(
641:c
632:T
625:e
614:)
611:e
608:(
605:c
600:T
594:e
586:=
583:)
576:T
567:T
564:(
561:g
549:—
537:T
517:)
514:G
511:(
507:E
500:F
475:)
472:e
469:(
466:c
461:T
455:F
449:e
438:)
435:e
432:(
429:c
424:T
418:F
412:e
404:=
401:)
398:F
395:(
392:g
365:T
344:T
324:F
304:)
301:e
298:(
295:c
290:T
284:e
259:)
256:e
253:(
250:c
241:T
234:e
205:T
196:T
193:=
190:F
167:)
164:G
161:(
157:E
146:T
125:)
122:G
119:(
115:E
108:T
88:)
85:c
82:,
79:G
76:(
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.