4761:, i.e. solving the LP formed by two constraints in the model and then seeking the cutting plane by adding inequality constraints to gradually converge at an optimal solution. When people apply this method to find a cutting plane, they often depend on experience, so this method is seldom used as a general method.
4772:
It controls the searching process through applying restrictive boundaries, allowing a search for the optimal solution branch from the space state tree to find an optimal solution as quickly as possible. The pivotal component of this algorithm is the selection of the restrictive boundary. Different
4781:
As the application of precise algorithm to solve problem is very limited, we often use approximate algorithm or heuristic algorithm. The result of the algorithm can be assessed by C / C* ≤ ε . C is the total travelling distance generated from approximate algorithm; C* is the optimal travelling
4768:
on the TSP, describing a technique of combining smaller search spaces and establishing lower bounds to enlarge the practical range of application for an exact solution. The technique is useful for expanding the number of cities able to be considered computationally, but still breaks down in
43:(TSP), in which the input is a distance matrix between a set of cities, and the goal is to find a minimum-length tour that visits each city exactly once before returning to the starting point. It finds the exact solution to this problem, and to several related problems including the
4782:
distance; ε is the upper limit for the ratio of the total travelling distance of approximate solution to optimal solution under the worst condition. The value of ε >1.0. The more it closes to 1.0, the better the algorithm is. These algorithms include: Interpolation algorithm,
3434:
1666:
3736:
1381:
4187:
2178:
1181:
1006:
962:
918:
3241:
117:
designated arbitrarily as a "starting" city (since the solution to TSP is a
Hamiltonian cycle, the choice of starting city doesn't matter). The Held–Karp algorithm begins by calculating, for each set of cities
4010:
4614:
874:
836:
755:
717:
2264:
3624:
3543:
632:
160:
4657:
2058:
1480:
2549:
2976:
2812:
2620:
524:
2919:
2691:
1291:
1059:
2296:
1532:
95:
679:
2581:
1245:
3489:
600:
1419:
1117:
4472:
3246:
186:
4507:
4273:
4045:
3874:
3063:
2734:
2655:
2435:
2371:
559:
489:
411:
336:
301:
3099:
3008:
1981:
1874:
1847:
1800:
1693:
4553:
4359:
3460:
2397:
3763:
4573:
4527:
4333:
4313:
4293:
3894:
3028:
2938:
2872:
2852:
2832:
2774:
2754:
2495:
2475:
2455:
2336:
2316:
1954:
1934:
1914:
1894:
1820:
1773:
1753:
1733:
1713:
1537:
1500:
1331:
1311:
1265:
1201:
1137:
1079:
798:
778:
454:
431:
376:
356:
266:
246:
226:
206:
115:
4227:
4207:
3831:
3811:
3787:
3629:
1336:
4240:
If only the length of the shortest cycle is needed, not the cycle itself, then space complexity can be improved somewhat by noting that calculating
4050:
4837:
4872:
2063:
1142:
967:
923:
879:
3104:
3899:
841:
803:
722:
684:
4578:
2186:
4867:
4783:
4757:
are design patterns also used for exact solutions to the TSP. Linear programming applies the cutting plane method in
3548:
3501:
40:
605:
121:
4619:
1986:
1427:
44:
2338:
that passes through every other city. The much shorter second stage adds these distances to the edge lengths
4787:
2508:
1802:
as its second-to-last city, then removing the final edge from this path must give the shortest path from
2402:
The shortest path itself (and not just its length), finally, may be reconstructed by storing alongside
3790:
2943:
2779:
2586:
494:
2660:
1270:
1011:
800:
rises quickly, but only a few such paths need to be examined to find the shortest. For instance, if
4844:
4791:
4758:
2877:
2269:
1505:
62:
28:
637:
4750:
3429:{\textstyle (n-1)(n-2)\sum _{k=1}^{n-2}{\binom {n-3}{k-1}}=(n-1)(n-2)2^{n-3}=\Theta (n^{2}2^{n})}
2554:
1206:
32:
3465:
564:
1386:
1084:
3833:. However, this is a constant factor improvement and does not affect asymptotic performance.
165:
4754:
4477:
4364:
4243:
4015:
3844:
3495:
3033:
2704:
2625:
2405:
2341:
529:
459:
381:
306:
271:
48:
4823:'A dynamic programming approach to sequencing problems’, Michael Held and Richard M. Karp,
3068:
2981:
1959:
1852:
1825:
1778:
1671:
1661:{\displaystyle S_{i}=S\setminus \{s_{i}\}=\{s_{1},\ldots ,s_{i-1},s_{i+1},\ldots ,s_{k}\}}
36:
4532:
4338:
3439:
2376:
4558:
4512:
4318:
4298:
4278:
3879:
3766:
3741:
3013:
2923:
2857:
2837:
2817:
2759:
2739:
2480:
2460:
2440:
2321:
2301:
1939:
1919:
1899:
1879:
1805:
1758:
1738:
1718:
1698:
1485:
1316:
1296:
1250:
1186:
1122:
1064:
783:
763:
439:
416:
361:
341:
251:
231:
211:
191:
100:
2854:
and an edge length from the original graph; that is, it requires time proportional to
4861:
4810:‘Dynamic programming treatment of the travelling salesman problem’, Richard Bellman,
3731:{\textstyle \{(S,e):|S|=\lfloor {\frac {n-1}{2}}\rfloor ,e\in S^{c}\setminus \{1\}\}}
4234:
4212:
4192:
3816:
3796:
3772:
1376:{\displaystyle 1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5\rightarrow 6}
4764:
The term branch and bound was first used in 1963 in a paper published by Little
4182:{\textstyle \sum _{k=0}^{n-2}(n-1){\binom {n-2}{k}}=(n-1)2^{n}=\Theta (n2^{n})}
4230:
268:
in some order (but not through any other cities). Denote this distance
2173:{\displaystyle g(S,e)=\min _{1\leq i\leq k}g(S_{i},s_{i})+d(s_{i},e)}
1176:{\displaystyle 1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5}
1001:{\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5}
957:{\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5}
913:{\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5}
491:
requires looking at one or two possible shortest paths. For example,
3236:{\textstyle k(n-k-1){\binom {n-1}{k}}=(n-1)(n-2){\binom {n-3}{k-1}}}
4773:
restrictive boundaries may form different branch-bound algorithms.
3436:. The second stage of the algorithm, finding a complete cycle from
4575:
reduces the algorithm's maximum space requirements, attained when
4786:, Clark & Wright algorithm, Double spanning tree algorithm,
4825:
Journal for the
Society for Industrial and Applied Mathematics
2551:, significantly better than the superexponential performance
4005:{\textstyle (n-k-1){\binom {n-1}{k}}=(n-1){\binom {n-2}{k}}}
780:
contains three or more cities, the number of paths through
1383:, and not any of the other five paths created by visiting
2583:
of a brute-force algorithm. Held–Karp, however, requires
4609:{\textstyle k=\left\lfloor {\frac {n}{2}}\right\rfloor }
2505:
The Held–Karp algorithm has exponential time complexity
2497:, raising space requirements by only a constant factor.
869:{\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4}
831:{\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4}
750:{\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4}
712:{\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4}
2399:
possible shortest cycles, and then finds the shortest.
4581:
4367:
4215:
4195:
4053:
3902:
3819:
3799:
3775:
3744:
3632:
3551:
3504:
3249:
3107:
2880:
2834:
possible paths, each found by adding a known value of
2437:
the label of the second-to-last city on the path from
4790:, Hybrid algorithm, Probabilistic algorithm (such as
4622:
4561:
4535:
4515:
4480:
4341:
4321:
4301:
4281:
4246:
4018:
3882:
3847:
3468:
3442:
3071:
3036:
3016:
2984:
2946:
2926:
2860:
2840:
2820:
2782:
2762:
2742:
2707:
2663:
2628:
2589:
2557:
2511:
2483:
2463:
2443:
2408:
2379:
2344:
2324:
2304:
2272:
2189:
2066:
1989:
1962:
1942:
1922:
1902:
1882:
1855:
1828:
1808:
1781:
1761:
1741:
1721:
1701:
1674:
1540:
1508:
1488:
1430:
1389:
1339:
1319:
1299:
1273:
1253:
1209:
1189:
1145:
1125:
1087:
1067:
1014:
970:
926:
882:
844:
806:
786:
766:
725:
687:
640:
608:
567:
532:
497:
462:
442:
419:
384:
364:
344:
309:
274:
254:
234:
214:
194:
168:
124:
103:
65:
2259:{\displaystyle g(\{2,\ldots ,i-1,i+1,\ldots ,n\},i)}
4651:
4608:
4567:
4547:
4521:
4501:
4466:
4353:
4327:
4307:
4287:
4267:
4221:
4201:
4181:
4039:
4004:
3888:
3868:
3825:
3805:
3781:
3757:
3730:
3618:
3537:
3483:
3454:
3428:
3235:
3093:
3057:
3022:
3002:
2970:
2932:
2913:
2866:
2846:
2826:
2806:
2768:
2748:
2728:
2685:
2649:
2622:space to hold all computed values of the function
2614:
2575:
2543:
2489:
2469:
2449:
2429:
2391:
2365:
2330:
2310:
2290:
2258:
2172:
2052:
1975:
1948:
1928:
1908:
1888:
1868:
1841:
1814:
1794:
1767:
1747:
1727:
1707:
1687:
1660:
1526:
1494:
1474:
1413:
1375:
1325:
1305:
1285:
1259:
1239:
1195:
1175:
1131:
1111:
1073:
1053:
1000:
956:
912:
868:
830:
792:
772:
749:
711:
673:
626:
594:
553:
518:
483:
448:
425:
405:
370:
350:
330:
295:
260:
240:
220:
200:
180:
154:
109:
89:
3491:time and does not affect asymptotic performance.
2089:
3619:{\textstyle g(S,e)+g(S^{c}\setminus \{1,e\},e)}
3538:{\textstyle k=\lfloor {\frac {n-1}{2}}\rfloor }
3498:, the algorithm can be stopped early after the
4453:
4432:
4420:
4391:
4120:
4099:
3996:
3975:
3948:
3927:
3339:
3310:
3227:
3198:
3156:
3135:
2905:
2884:
8:
3725:
3722:
3716:
3691:
3670:
3633:
3604:
3592:
3532:
3511:
2965:
2947:
2801:
2783:
2244:
2196:
1956:, one for each possible second-to-last city
1655:
1579:
1573:
1560:
1469:
1437:
1408:
1390:
1234:
1210:
1106:
1088:
1039:
1021:
659:
647:
580:
574:
456:has two or fewer elements, then calculating
149:
131:
31:algorithm proposed in 1962 independently by
3243:, for a total time across all subset sizes
627:{\displaystyle 1\rightarrow 2\rightarrow 3}
4777:Approximate algorithms for solving the TSP
2183:This stage of the algorithm finishes when
155:{\displaystyle S\subseteq \{2,\ldots ,n\}}
16:Solution of the traveling salesman problem
4652:{\displaystyle \Theta ({\sqrt {n}}2^{n})}
4640:
4629:
4621:
4592:
4580:
4560:
4534:
4514:
4479:
4452:
4431:
4429:
4419:
4390:
4388:
4366:
4340:
4320:
4300:
4280:
4245:
4214:
4194:
4170:
4148:
4119:
4098:
4096:
4069:
4058:
4052:
4017:
3995:
3974:
3972:
3947:
3926:
3924:
3901:
3881:
3846:
3818:
3798:
3774:
3749:
3743:
3707:
3673:
3662:
3654:
3631:
3583:
3550:
3514:
3503:
3467:
3441:
3417:
3407:
3382:
3338:
3309:
3307:
3295:
3284:
3248:
3226:
3197:
3195:
3155:
3134:
3132:
3106:
3080:
3072:
3070:
3035:
3015:
2983:
2945:
2925:
2904:
2883:
2881:
2879:
2859:
2839:
2819:
2781:
2761:
2741:
2706:
2674:
2662:
2627:
2603:
2588:
2556:
2532:
2522:
2510:
2482:
2462:
2442:
2407:
2378:
2343:
2323:
2303:
2298:, giving the shortest distance from city
2271:
2188:
2155:
2133:
2120:
2092:
2065:
2053:{\displaystyle g(S_{i},s_{i})+d(s_{i},e)}
2035:
2013:
2000:
1988:
1967:
1961:
1941:
1921:
1901:
1881:
1860:
1854:
1833:
1827:
1807:
1786:
1780:
1760:
1740:
1720:
1700:
1679:
1673:
1649:
1624:
1605:
1586:
1567:
1545:
1539:
1507:
1487:
1475:{\displaystyle S=\{s_{1},\ldots ,s_{k}\}}
1463:
1444:
1429:
1388:
1338:
1318:
1298:
1272:
1252:
1208:
1188:
1144:
1124:
1086:
1066:
1013:
969:
925:
881:
843:
805:
785:
765:
724:
686:
639:
607:
566:
531:
496:
461:
441:
418:
383:
363:
343:
308:
273:
253:
233:
213:
193:
167:
123:
102:
64:
4803:
4209:is sufficiently small enough such that
3713:
3589:
1557:
1061:. Similarly, if the shortest path from
338:for the length of the direct edge from
4012:values. A complete table of values of
7:
4745:Exact algorithms for solving the TSP
55:Algorithm description and motivation
4237:, rather than an explicit k-tuple.
2544:{\displaystyle \Theta (2^{n}n^{2})}
4623:
4436:
4395:
4157:
4103:
3979:
3931:
3469:
3397:
3314:
3202:
3139:
2888:
2664:
2590:
2558:
2512:
504:
248:that passes through every city in
14:
4812:Journal of Assoc. Computing Mach.
2814:requires finding the shortest of
2693:space to store the graph itself.
1715:. Then if the shortest path from
208:, the shortest one-way path from
1668:for the set created by removing
433:and finishing with the largest.
413:starting with the smallest sets
2971:{\displaystyle \{2,\ldots ,n\}}
2807:{\displaystyle \{2,\ldots ,n\}}
2657:, while brute force needs only
2615:{\displaystyle \Theta (n2^{n})}
519:{\displaystyle g(\emptyset ,e)}
4843:. January 2020. Archived from
4684:g({k}, k) := d(1, k)
4646:
4626:
4496:
4484:
4380:
4368:
4262:
4250:
4176:
4160:
4141:
4129:
4093:
4081:
4034:
4022:
3969:
3957:
3921:
3903:
3863:
3851:
3663:
3655:
3648:
3636:
3613:
3576:
3567:
3555:
3545:step, and finding the minimum
3478:
3472:
3423:
3400:
3375:
3363:
3360:
3348:
3277:
3265:
3262:
3250:
3192:
3180:
3177:
3165:
3129:
3111:
3081:
3073:
3052:
3040:
2914:{\textstyle {\binom {n-1}{k}}}
2723:
2711:
2686:{\displaystyle \Theta (n^{2})}
2680:
2667:
2644:
2632:
2609:
2593:
2570:
2561:
2538:
2515:
2424:
2412:
2360:
2348:
2253:
2193:
2167:
2148:
2139:
2113:
2082:
2070:
2047:
2028:
2019:
1993:
1367:
1361:
1355:
1349:
1343:
1286:{\displaystyle 5\rightarrow 6}
1277:
1167:
1161:
1155:
1149:
1054:{\displaystyle g(\{2,3,4\},5)}
1048:
1018:
992:
986:
980:
974:
948:
942:
936:
930:
904:
898:
892:
886:
860:
854:
848:
822:
816:
810:
741:
735:
729:
703:
697:
691:
668:
644:
618:
612:
589:
571:
548:
536:
513:
501:
478:
466:
400:
388:
325:
313:
290:
278:
1:
4749:Besides Dynamic Programming,
2291:{\displaystyle 2\leq i\leq n}
1896:possible shortest paths from
1527:{\displaystyle 1\leq i\leq k}
1183:, and the shortest path from
90:{\displaystyle 1,2,\ldots ,n}
1876:. This means there are only
674:{\displaystyle g(\{2,3\},4)}
4873:Travelling salesman problem
4784:Nearest neighbour algorithm
2576:{\displaystyle \Theta (n!)}
2266:is known for every integer
1293:, then the whole path from
1240:{\displaystyle \{2,3,4,5\}}
1008:is not a possible value of
25:Bellman–Held–Karp algorithm
4889:
3484:{\displaystyle \Theta (n)}
3030:. Computing all values of
1502:cities. For every integer
595:{\displaystyle g(\{2\},3)}
378:. We'll compute values of
41:traveling salesman problem
4702:S ⊆ {2, ..., n}, |S| = s
3789:. This is analogous to a
1414:{\displaystyle \{2,3,4\}}
1112:{\displaystyle \{2,3,4\}}
45:Hamiltonian cycle problem
4315:requires only values of
4233:of constant multiple of
3813:and meeting at midpoint
2978:; and each subset gives
1424:More generally, suppose
757:, whichever is shorter.
681:is the length of either
4769:large-scale data sets.
4467:{\textstyle (n-1)\left}
2701:Computing one value of
181:{\displaystyle e\neq 1}
4788:Christofides algorithm
4653:
4610:
4569:
4549:
4523:
4503:
4502:{\displaystyle g(S,e)}
4468:
4355:
4329:
4309:
4289:
4269:
4268:{\displaystyle g(S,e)}
4223:
4203:
4183:
4080:
4041:
4040:{\displaystyle g(S,e)}
4006:
3890:
3870:
3869:{\displaystyle g(S,e)}
3841:Storing all values of
3827:
3807:
3783:
3759:
3732:
3620:
3539:
3485:
3456:
3430:
3306:
3237:
3095:
3059:
3058:{\displaystyle g(S,e)}
3024:
3004:
2972:
2934:
2915:
2868:
2848:
2828:
2808:
2770:
2750:
2730:
2729:{\displaystyle g(S,e)}
2687:
2651:
2650:{\displaystyle g(S,e)}
2616:
2577:
2545:
2501:Algorithmic complexity
2491:
2471:
2451:
2431:
2430:{\displaystyle g(S,e)}
2393:
2367:
2366:{\displaystyle d(i,1)}
2332:
2312:
2292:
2260:
2174:
2054:
1977:
1950:
1930:
1910:
1890:
1870:
1843:
1816:
1796:
1769:
1749:
1729:
1709:
1689:
1662:
1528:
1496:
1476:
1421:in a different order.
1415:
1377:
1327:
1307:
1287:
1261:
1241:
1197:
1177:
1133:
1113:
1075:
1055:
1002:
958:
914:
870:
832:
794:
774:
751:
713:
675:
628:
602:is just the length of
596:
555:
554:{\displaystyle d(1,e)}
520:
485:
484:{\displaystyle g(S,e)}
450:
427:
407:
406:{\displaystyle g(S,e)}
372:
352:
332:
331:{\displaystyle d(u,v)}
297:
296:{\displaystyle g(S,e)}
262:
242:
222:
202:
182:
156:
111:
91:
4838:"Dynamic programming"
4673:algorithm TSP (G, n)
4654:
4611:
4570:
4550:
4524:
4504:
4469:
4356:
4330:
4310:
4290:
4270:
4224:
4204:
4184:
4054:
4042:
4007:
3891:
3871:
3828:
3808:
3784:
3760:
3733:
3621:
3540:
3486:
3457:
3431:
3280:
3238:
3096:
3094:{\displaystyle |S|=k}
3060:
3025:
3005:
3003:{\displaystyle n-k-1}
2973:
2935:
2916:
2869:
2849:
2829:
2809:
2771:
2751:
2731:
2688:
2652:
2617:
2578:
2546:
2492:
2472:
2452:
2432:
2394:
2368:
2333:
2313:
2293:
2261:
2175:
2055:
1978:
1976:{\displaystyle s_{i}}
1951:
1931:
1911:
1891:
1871:
1869:{\displaystyle S_{i}}
1844:
1842:{\displaystyle s_{i}}
1817:
1797:
1795:{\displaystyle s_{i}}
1770:
1750:
1730:
1710:
1690:
1688:{\displaystyle s_{i}}
1663:
1529:
1497:
1477:
1416:
1378:
1328:
1308:
1288:
1262:
1242:
1198:
1178:
1134:
1114:
1076:
1056:
1003:
959:
920:must be shorter than
915:
871:
833:
795:
775:
752:
714:
676:
629:
597:
556:
521:
486:
451:
428:
408:
373:
353:
333:
298:
263:
243:
223:
203:
183:
157:
112:
92:
4620:
4579:
4559:
4533:
4513:
4478:
4365:
4339:
4335:for subsets of size
4319:
4299:
4279:
4244:
4213:
4193:
4189:. This assumes that
4051:
4047:thus requires space
4016:
3900:
3880:
3876:for subsets of size
3845:
3817:
3797:
3791:bidirectional search
3773:
3742:
3630:
3549:
3502:
3466:
3440:
3247:
3105:
3069:
3034:
3014:
2982:
2944:
2940:-element subsets of
2924:
2878:
2858:
2838:
2818:
2780:
2760:
2740:
2705:
2661:
2626:
2587:
2555:
2509:
2481:
2461:
2441:
2406:
2377:
2342:
2322:
2302:
2270:
2187:
2064:
1987:
1960:
1940:
1920:
1900:
1880:
1853:
1826:
1806:
1779:
1759:
1739:
1719:
1699:
1672:
1538:
1506:
1486:
1428:
1387:
1337:
1317:
1297:
1271:
1251:
1207:
1187:
1143:
1123:
1085:
1065:
1012:
968:
964:, and the length of
924:
880:
842:
804:
784:
764:
723:
685:
638:
606:
565:
530:
495:
460:
440:
417:
382:
362:
342:
307:
272:
252:
232:
212:
192:
166:
122:
101:
63:
4868:Dynamic programming
4792:Simulated annealing
4759:integer programming
4713:g(S, k) := min
4548:{\displaystyle k-1}
4361:. Keeping only the
4354:{\displaystyle k-1}
4229:can be stored as a
3455:{\displaystyle n-1}
3101:thus requires time
3010:possible values of
2392:{\displaystyle n-1}
1267:ends with the edge
29:dynamic programming
21:Held–Karp algorithm
4751:Linear programming
4740:Related algorithms
4649:
4606:
4565:
4545:
4519:
4499:
4464:
4351:
4325:
4305:
4285:
4265:
4219:
4199:
4179:
4037:
4002:
3886:
3866:
3823:
3803:
3779:
3758:{\textstyle S^{c}}
3755:
3728:
3616:
3535:
3481:
3462:candidates, takes
3452:
3426:
3233:
3091:
3055:
3020:
3000:
2968:
2930:
2911:
2864:
2844:
2824:
2804:
2766:
2746:
2726:
2683:
2647:
2612:
2573:
2541:
2487:
2467:
2447:
2427:
2389:
2363:
2328:
2308:
2288:
2256:
2170:
2109:
2050:
1973:
1946:
1926:
1906:
1886:
1866:
1839:
1812:
1792:
1765:
1745:
1725:
1705:
1685:
1658:
1524:
1492:
1472:
1411:
1373:
1323:
1303:
1283:
1257:
1237:
1193:
1173:
1129:
1109:
1071:
1051:
998:
954:
910:
866:
828:
790:
770:
747:
709:
671:
624:
592:
551:
516:
481:
446:
423:
403:
368:
348:
328:
293:
258:
238:
218:
198:
178:
152:
107:
87:
59:Number the cities
23:, also called the
4680:k := 2 to n
4634:
4600:
4568:{\displaystyle k}
4522:{\displaystyle S}
4451:
4418:
4328:{\displaystyle g}
4308:{\displaystyle k}
4288:{\displaystyle S}
4118:
3994:
3946:
3896:requires keeping
3889:{\displaystyle k}
3689:
3530:
3496:undirected graphs
3337:
3225:
3154:
3023:{\displaystyle e}
2933:{\displaystyle k}
2903:
2867:{\displaystyle k}
2847:{\displaystyle g}
2827:{\displaystyle k}
2769:{\displaystyle S}
2749:{\displaystyle k}
2490:{\displaystyle S}
2470:{\displaystyle e}
2450:{\displaystyle 1}
2331:{\displaystyle i}
2311:{\displaystyle 1}
2088:
1949:{\displaystyle S}
1929:{\displaystyle e}
1909:{\displaystyle 1}
1889:{\displaystyle k}
1815:{\displaystyle 1}
1768:{\displaystyle e}
1748:{\displaystyle S}
1728:{\displaystyle 1}
1708:{\displaystyle S}
1495:{\displaystyle k}
1326:{\displaystyle 6}
1306:{\displaystyle 1}
1260:{\displaystyle 6}
1196:{\displaystyle 1}
1132:{\displaystyle 5}
1074:{\displaystyle 1}
793:{\displaystyle S}
773:{\displaystyle S}
449:{\displaystyle S}
426:{\displaystyle S}
371:{\displaystyle v}
351:{\displaystyle u}
261:{\displaystyle S}
241:{\displaystyle e}
221:{\displaystyle 1}
201:{\displaystyle S}
188:not contained in
110:{\displaystyle 1}
4880:
4852:
4851:
4849:
4842:
4834:
4828:
4821:
4815:
4808:
4755:Branch and bound
4658:
4656:
4655:
4650:
4645:
4644:
4635:
4630:
4615:
4613:
4612:
4607:
4605:
4601:
4593:
4574:
4572:
4571:
4566:
4554:
4552:
4551:
4546:
4529:has size either
4528:
4526:
4525:
4520:
4508:
4506:
4505:
4500:
4473:
4471:
4470:
4465:
4463:
4459:
4458:
4457:
4456:
4447:
4435:
4425:
4424:
4423:
4417:
4406:
4394:
4360:
4358:
4357:
4352:
4334:
4332:
4331:
4326:
4314:
4312:
4311:
4306:
4294:
4292:
4291:
4286:
4274:
4272:
4271:
4266:
4228:
4226:
4225:
4220:
4208:
4206:
4205:
4200:
4188:
4186:
4185:
4180:
4175:
4174:
4153:
4152:
4125:
4124:
4123:
4114:
4102:
4079:
4068:
4046:
4044:
4043:
4038:
4011:
4009:
4008:
4003:
4001:
4000:
3999:
3990:
3978:
3953:
3952:
3951:
3942:
3930:
3895:
3893:
3892:
3887:
3875:
3873:
3872:
3867:
3832:
3830:
3829:
3824:
3812:
3810:
3809:
3804:
3788:
3786:
3785:
3780:
3764:
3762:
3761:
3756:
3754:
3753:
3737:
3735:
3734:
3729:
3712:
3711:
3690:
3685:
3674:
3666:
3658:
3625:
3623:
3622:
3617:
3588:
3587:
3544:
3542:
3541:
3536:
3531:
3526:
3515:
3490:
3488:
3487:
3482:
3461:
3459:
3458:
3453:
3435:
3433:
3432:
3427:
3422:
3421:
3412:
3411:
3393:
3392:
3344:
3343:
3342:
3336:
3325:
3313:
3305:
3294:
3242:
3240:
3239:
3234:
3232:
3231:
3230:
3224:
3213:
3201:
3161:
3160:
3159:
3150:
3138:
3100:
3098:
3097:
3092:
3084:
3076:
3064:
3062:
3061:
3056:
3029:
3027:
3026:
3021:
3009:
3007:
3006:
3001:
2977:
2975:
2974:
2969:
2939:
2937:
2936:
2931:
2920:
2918:
2917:
2912:
2910:
2909:
2908:
2899:
2887:
2873:
2871:
2870:
2865:
2853:
2851:
2850:
2845:
2833:
2831:
2830:
2825:
2813:
2811:
2810:
2805:
2775:
2773:
2772:
2767:
2756:-element subset
2755:
2753:
2752:
2747:
2735:
2733:
2732:
2727:
2692:
2690:
2689:
2684:
2679:
2678:
2656:
2654:
2653:
2648:
2621:
2619:
2618:
2613:
2608:
2607:
2582:
2580:
2579:
2574:
2550:
2548:
2547:
2542:
2537:
2536:
2527:
2526:
2496:
2494:
2493:
2488:
2476:
2474:
2473:
2468:
2456:
2454:
2453:
2448:
2436:
2434:
2433:
2428:
2398:
2396:
2395:
2390:
2372:
2370:
2369:
2364:
2337:
2335:
2334:
2329:
2317:
2315:
2314:
2309:
2297:
2295:
2294:
2289:
2265:
2263:
2262:
2257:
2179:
2177:
2176:
2171:
2160:
2159:
2138:
2137:
2125:
2124:
2108:
2059:
2057:
2056:
2051:
2040:
2039:
2018:
2017:
2005:
2004:
1982:
1980:
1979:
1974:
1972:
1971:
1955:
1953:
1952:
1947:
1935:
1933:
1932:
1927:
1915:
1913:
1912:
1907:
1895:
1893:
1892:
1887:
1875:
1873:
1872:
1867:
1865:
1864:
1848:
1846:
1845:
1840:
1838:
1837:
1821:
1819:
1818:
1813:
1801:
1799:
1798:
1793:
1791:
1790:
1774:
1772:
1771:
1766:
1754:
1752:
1751:
1746:
1734:
1732:
1731:
1726:
1714:
1712:
1711:
1706:
1694:
1692:
1691:
1686:
1684:
1683:
1667:
1665:
1664:
1659:
1654:
1653:
1635:
1634:
1616:
1615:
1591:
1590:
1572:
1571:
1550:
1549:
1533:
1531:
1530:
1525:
1501:
1499:
1498:
1493:
1481:
1479:
1478:
1473:
1468:
1467:
1449:
1448:
1420:
1418:
1417:
1412:
1382:
1380:
1379:
1374:
1332:
1330:
1329:
1324:
1312:
1310:
1309:
1304:
1292:
1290:
1289:
1284:
1266:
1264:
1263:
1258:
1246:
1244:
1243:
1238:
1202:
1200:
1199:
1194:
1182:
1180:
1179:
1174:
1138:
1136:
1135:
1130:
1118:
1116:
1115:
1110:
1080:
1078:
1077:
1072:
1060:
1058:
1057:
1052:
1007:
1005:
1004:
999:
963:
961:
960:
955:
919:
917:
916:
911:
875:
873:
872:
867:
838:is shorter than
837:
835:
834:
829:
799:
797:
796:
791:
779:
777:
776:
771:
756:
754:
753:
748:
718:
716:
715:
710:
680:
678:
677:
672:
633:
631:
630:
625:
601:
599:
598:
593:
560:
558:
557:
552:
525:
523:
522:
517:
490:
488:
487:
482:
455:
453:
452:
447:
432:
430:
429:
424:
412:
410:
409:
404:
377:
375:
374:
369:
357:
355:
354:
349:
337:
335:
334:
329:
302:
300:
299:
294:
267:
265:
264:
259:
247:
245:
244:
239:
227:
225:
224:
219:
207:
205:
204:
199:
187:
185:
184:
179:
161:
159:
158:
153:
116:
114:
113:
108:
96:
94:
93:
88:
49:exponential time
35:and by Held and
4888:
4887:
4883:
4882:
4881:
4879:
4878:
4877:
4858:
4857:
4856:
4855:
4847:
4840:
4836:
4835:
4831:
4822:
4818:
4809:
4805:
4800:
4779:
4747:
4742:
4737:
4729:
4726:opt := min
4716:
4665:
4636:
4618:
4617:
4588:
4577:
4576:
4557:
4556:
4531:
4530:
4511:
4510:
4476:
4475:
4437:
4430:
4407:
4396:
4389:
4387:
4383:
4363:
4362:
4337:
4336:
4317:
4316:
4297:
4296:
4277:
4276:
4242:
4241:
4211:
4210:
4191:
4190:
4166:
4144:
4104:
4097:
4049:
4048:
4014:
4013:
3980:
3973:
3932:
3925:
3898:
3897:
3878:
3877:
3843:
3842:
3839:
3815:
3814:
3795:
3794:
3771:
3770:
3745:
3740:
3739:
3703:
3675:
3628:
3627:
3579:
3547:
3546:
3516:
3500:
3499:
3464:
3463:
3438:
3437:
3413:
3403:
3378:
3326:
3315:
3308:
3245:
3244:
3214:
3203:
3196:
3140:
3133:
3103:
3102:
3067:
3066:
3032:
3031:
3012:
3011:
2980:
2979:
2942:
2941:
2922:
2921:
2889:
2882:
2876:
2875:
2856:
2855:
2836:
2835:
2816:
2815:
2778:
2777:
2758:
2757:
2738:
2737:
2703:
2702:
2699:
2670:
2659:
2658:
2624:
2623:
2599:
2585:
2584:
2553:
2552:
2528:
2518:
2507:
2506:
2503:
2479:
2478:
2459:
2458:
2439:
2438:
2404:
2403:
2375:
2374:
2340:
2339:
2320:
2319:
2300:
2299:
2268:
2267:
2185:
2184:
2151:
2129:
2116:
2062:
2061:
2031:
2009:
1996:
1985:
1984:
1963:
1958:
1957:
1938:
1937:
1918:
1917:
1898:
1897:
1878:
1877:
1856:
1851:
1850:
1829:
1824:
1823:
1804:
1803:
1782:
1777:
1776:
1757:
1756:
1737:
1736:
1717:
1716:
1697:
1696:
1675:
1670:
1669:
1645:
1620:
1601:
1582:
1563:
1541:
1536:
1535:
1504:
1503:
1484:
1483:
1459:
1440:
1426:
1425:
1385:
1384:
1335:
1334:
1315:
1314:
1295:
1294:
1269:
1268:
1249:
1248:
1205:
1204:
1185:
1184:
1141:
1140:
1121:
1120:
1083:
1082:
1063:
1062:
1010:
1009:
966:
965:
922:
921:
878:
877:
840:
839:
802:
801:
782:
781:
762:
761:
721:
720:
683:
682:
636:
635:
604:
603:
563:
562:
528:
527:
493:
492:
458:
457:
438:
437:
415:
414:
380:
379:
360:
359:
340:
339:
305:
304:
270:
269:
250:
249:
230:
229:
210:
209:
190:
189:
164:
163:
162:and every city
120:
119:
99:
98:
61:
60:
57:
17:
12:
11:
5:
4886:
4884:
4876:
4875:
4870:
4860:
4859:
4854:
4853:
4850:on 2015-02-08.
4829:
4816:
4802:
4801:
4799:
4796:
4778:
4775:
4746:
4743:
4741:
4738:
4727:
4714:
4669:
4664:
4661:
4648:
4643:
4639:
4633:
4628:
4625:
4604:
4599:
4596:
4591:
4587:
4584:
4564:
4544:
4541:
4538:
4518:
4498:
4495:
4492:
4489:
4486:
4483:
4462:
4455:
4450:
4446:
4443:
4440:
4434:
4428:
4422:
4416:
4413:
4410:
4405:
4402:
4399:
4393:
4386:
4382:
4379:
4376:
4373:
4370:
4350:
4347:
4344:
4324:
4304:
4284:
4264:
4261:
4258:
4255:
4252:
4249:
4222:{\textstyle S}
4218:
4202:{\textstyle n}
4198:
4178:
4173:
4169:
4165:
4162:
4159:
4156:
4151:
4147:
4143:
4140:
4137:
4134:
4131:
4128:
4122:
4117:
4113:
4110:
4107:
4101:
4095:
4092:
4089:
4086:
4083:
4078:
4075:
4072:
4067:
4064:
4061:
4057:
4036:
4033:
4030:
4027:
4024:
4021:
3998:
3993:
3989:
3986:
3983:
3977:
3971:
3968:
3965:
3962:
3959:
3956:
3950:
3945:
3941:
3938:
3935:
3929:
3923:
3920:
3917:
3914:
3911:
3908:
3905:
3885:
3865:
3862:
3859:
3856:
3853:
3850:
3838:
3835:
3826:{\textstyle e}
3822:
3806:{\textstyle 1}
3802:
3782:{\textstyle S}
3778:
3767:complement set
3752:
3748:
3727:
3724:
3721:
3718:
3715:
3710:
3706:
3702:
3699:
3696:
3693:
3688:
3684:
3681:
3678:
3672:
3669:
3665:
3661:
3657:
3653:
3650:
3647:
3644:
3641:
3638:
3635:
3615:
3612:
3609:
3606:
3603:
3600:
3597:
3594:
3591:
3586:
3582:
3578:
3575:
3572:
3569:
3566:
3563:
3560:
3557:
3554:
3534:
3529:
3525:
3522:
3519:
3513:
3510:
3507:
3480:
3477:
3474:
3471:
3451:
3448:
3445:
3425:
3420:
3416:
3410:
3406:
3402:
3399:
3396:
3391:
3388:
3385:
3381:
3377:
3374:
3371:
3368:
3365:
3362:
3359:
3356:
3353:
3350:
3347:
3341:
3335:
3332:
3329:
3324:
3321:
3318:
3312:
3304:
3301:
3298:
3293:
3290:
3287:
3283:
3279:
3276:
3273:
3270:
3267:
3264:
3261:
3258:
3255:
3252:
3229:
3223:
3220:
3217:
3212:
3209:
3206:
3200:
3194:
3191:
3188:
3185:
3182:
3179:
3176:
3173:
3170:
3167:
3164:
3158:
3153:
3149:
3146:
3143:
3137:
3131:
3128:
3125:
3122:
3119:
3116:
3113:
3110:
3090:
3087:
3083:
3079:
3075:
3054:
3051:
3048:
3045:
3042:
3039:
3019:
2999:
2996:
2993:
2990:
2987:
2967:
2964:
2961:
2958:
2955:
2952:
2949:
2929:
2907:
2902:
2898:
2895:
2892:
2886:
2863:
2843:
2823:
2803:
2800:
2797:
2794:
2791:
2788:
2785:
2765:
2745:
2725:
2722:
2719:
2716:
2713:
2710:
2698:
2695:
2682:
2677:
2673:
2669:
2666:
2646:
2643:
2640:
2637:
2634:
2631:
2611:
2606:
2602:
2598:
2595:
2592:
2572:
2569:
2566:
2563:
2560:
2540:
2535:
2531:
2525:
2521:
2517:
2514:
2502:
2499:
2486:
2466:
2446:
2426:
2423:
2420:
2417:
2414:
2411:
2388:
2385:
2382:
2362:
2359:
2356:
2353:
2350:
2347:
2327:
2307:
2287:
2284:
2281:
2278:
2275:
2255:
2252:
2249:
2246:
2243:
2240:
2237:
2234:
2231:
2228:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2169:
2166:
2163:
2158:
2154:
2150:
2147:
2144:
2141:
2136:
2132:
2128:
2123:
2119:
2115:
2112:
2107:
2104:
2101:
2098:
2095:
2091:
2087:
2084:
2081:
2078:
2075:
2072:
2069:
2049:
2046:
2043:
2038:
2034:
2030:
2027:
2024:
2021:
2016:
2012:
2008:
2003:
1999:
1995:
1992:
1970:
1966:
1945:
1925:
1905:
1885:
1863:
1859:
1836:
1832:
1811:
1789:
1785:
1764:
1744:
1724:
1704:
1682:
1678:
1657:
1652:
1648:
1644:
1641:
1638:
1633:
1630:
1627:
1623:
1619:
1614:
1611:
1608:
1604:
1600:
1597:
1594:
1589:
1585:
1581:
1578:
1575:
1570:
1566:
1562:
1559:
1556:
1553:
1548:
1544:
1523:
1520:
1517:
1514:
1511:
1491:
1471:
1466:
1462:
1458:
1455:
1452:
1447:
1443:
1439:
1436:
1433:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1351:
1348:
1345:
1342:
1322:
1302:
1282:
1279:
1276:
1256:
1236:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1192:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1128:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1070:
1050:
1047:
1044:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
997:
994:
991:
988:
985:
982:
979:
976:
973:
953:
950:
947:
944:
941:
938:
935:
932:
929:
909:
906:
903:
900:
897:
894:
891:
888:
885:
865:
862:
859:
856:
853:
850:
847:
827:
824:
821:
818:
815:
812:
809:
789:
769:
746:
743:
740:
737:
734:
731:
728:
708:
705:
702:
699:
696:
693:
690:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
623:
620:
617:
614:
611:
591:
588:
585:
582:
579:
576:
573:
570:
550:
547:
544:
541:
538:
535:
515:
512:
509:
506:
503:
500:
480:
477:
474:
471:
468:
465:
445:
422:
402:
399:
396:
393:
390:
387:
367:
347:
327:
324:
321:
318:
315:
312:
292:
289:
286:
283:
280:
277:
257:
237:
217:
197:
177:
174:
171:
151:
148:
145:
142:
139:
136:
133:
130:
127:
106:
86:
83:
80:
77:
74:
71:
68:
56:
53:
15:
13:
10:
9:
6:
4:
3:
2:
4885:
4874:
4871:
4869:
4866:
4865:
4863:
4846:
4839:
4833:
4830:
4826:
4820:
4817:
4813:
4807:
4804:
4797:
4795:
4793:
4789:
4785:
4776:
4774:
4770:
4767:
4762:
4760:
4756:
4752:
4744:
4739:
4736:
4732:
4725:
4722:
4719:
4712:
4708:
4705:
4701:
4698:
4694:
4690:
4687:
4683:
4679:
4676:
4672:
4668:
4662:
4660:
4641:
4637:
4631:
4602:
4597:
4594:
4589:
4585:
4582:
4562:
4542:
4539:
4536:
4516:
4493:
4490:
4487:
4481:
4460:
4448:
4444:
4441:
4438:
4426:
4414:
4411:
4408:
4403:
4400:
4397:
4384:
4377:
4374:
4371:
4348:
4345:
4342:
4322:
4302:
4282:
4259:
4256:
4253:
4247:
4238:
4236:
4235:machine words
4232:
4216:
4196:
4171:
4167:
4163:
4154:
4149:
4145:
4138:
4135:
4132:
4126:
4115:
4111:
4108:
4105:
4090:
4087:
4084:
4076:
4073:
4070:
4065:
4062:
4059:
4055:
4031:
4028:
4025:
4019:
3991:
3987:
3984:
3981:
3966:
3963:
3960:
3954:
3943:
3939:
3936:
3933:
3918:
3915:
3912:
3909:
3906:
3883:
3860:
3857:
3854:
3848:
3836:
3834:
3820:
3800:
3792:
3776:
3768:
3750:
3746:
3719:
3708:
3704:
3700:
3697:
3694:
3686:
3682:
3679:
3676:
3667:
3659:
3651:
3645:
3642:
3639:
3610:
3607:
3601:
3598:
3595:
3584:
3580:
3573:
3570:
3564:
3561:
3558:
3552:
3527:
3523:
3520:
3517:
3508:
3505:
3497:
3492:
3475:
3449:
3446:
3443:
3418:
3414:
3408:
3404:
3394:
3389:
3386:
3383:
3379:
3372:
3369:
3366:
3357:
3354:
3351:
3345:
3333:
3330:
3327:
3322:
3319:
3316:
3302:
3299:
3296:
3291:
3288:
3285:
3281:
3274:
3271:
3268:
3259:
3256:
3253:
3221:
3218:
3215:
3210:
3207:
3204:
3189:
3186:
3183:
3174:
3171:
3168:
3162:
3151:
3147:
3144:
3141:
3126:
3123:
3120:
3117:
3114:
3108:
3088:
3085:
3077:
3049:
3046:
3043:
3037:
3017:
2997:
2994:
2991:
2988:
2985:
2962:
2959:
2956:
2953:
2950:
2927:
2900:
2896:
2893:
2890:
2861:
2841:
2821:
2798:
2795:
2792:
2789:
2786:
2763:
2743:
2720:
2717:
2714:
2708:
2696:
2694:
2675:
2671:
2641:
2638:
2635:
2629:
2604:
2600:
2596:
2567:
2564:
2533:
2529:
2523:
2519:
2500:
2498:
2484:
2464:
2444:
2421:
2418:
2415:
2409:
2400:
2386:
2383:
2380:
2357:
2354:
2351:
2345:
2325:
2305:
2285:
2282:
2279:
2276:
2273:
2250:
2247:
2241:
2238:
2235:
2232:
2229:
2226:
2223:
2220:
2217:
2214:
2211:
2208:
2205:
2202:
2199:
2190:
2181:
2164:
2161:
2156:
2152:
2145:
2142:
2134:
2130:
2126:
2121:
2117:
2110:
2105:
2102:
2099:
2096:
2093:
2085:
2079:
2076:
2073:
2067:
2044:
2041:
2036:
2032:
2025:
2022:
2014:
2010:
2006:
2001:
1997:
1990:
1968:
1964:
1943:
1923:
1903:
1883:
1861:
1857:
1834:
1830:
1809:
1787:
1783:
1762:
1742:
1722:
1702:
1680:
1676:
1650:
1646:
1642:
1639:
1636:
1631:
1628:
1625:
1621:
1617:
1612:
1609:
1606:
1602:
1598:
1595:
1592:
1587:
1583:
1576:
1568:
1564:
1554:
1551:
1546:
1542:
1521:
1518:
1515:
1512:
1509:
1489:
1464:
1460:
1456:
1453:
1450:
1445:
1441:
1434:
1431:
1422:
1405:
1402:
1399:
1396:
1393:
1370:
1364:
1358:
1352:
1346:
1340:
1320:
1300:
1280:
1274:
1254:
1231:
1228:
1225:
1222:
1219:
1216:
1213:
1190:
1170:
1164:
1158:
1152:
1146:
1126:
1103:
1100:
1097:
1094:
1091:
1068:
1045:
1042:
1036:
1033:
1030:
1027:
1024:
1015:
995:
989:
983:
977:
971:
951:
945:
939:
933:
927:
907:
901:
895:
889:
883:
863:
857:
851:
845:
825:
819:
813:
807:
787:
767:
758:
744:
738:
732:
726:
706:
700:
694:
688:
665:
662:
656:
653:
650:
641:
621:
615:
609:
586:
583:
577:
568:
545:
542:
539:
533:
510:
507:
498:
475:
472:
469:
463:
443:
434:
420:
397:
394:
391:
385:
365:
345:
322:
319:
316:
310:
287:
284:
281:
275:
255:
235:
215:
195:
175:
172:
169:
146:
143:
140:
137:
134:
128:
125:
104:
84:
81:
78:
75:
72:
69:
66:
54:
52:
50:
46:
42:
39:to solve the
38:
34:
30:
26:
22:
4845:the original
4832:
4824:
4819:
4811:
4806:
4780:
4771:
4765:
4763:
4748:
4735:end function
4734:
4730:
4723:
4720:
4717:
4710:
4706:
4703:
4699:
4696:
4692:
4691:s := 2
4688:
4685:
4681:
4677:
4674:
4670:
4666:
4239:
3840:
3793:starting at
3493:
2874:. There are
2700:
2504:
2401:
2182:
1983:with length
1482:is a set of
1423:
759:
634:. Likewise,
435:
303:, and write
58:
24:
20:
18:
4862:Categories
4827:1:10. 1962
4798:References
4663:Pseudocode
4474:values of
3626:for every
526:is simply
4624:Θ
4540:−
4442:−
4412:−
4401:−
4375:−
4346:−
4158:Θ
4136:−
4109:−
4088:−
4074:−
4056:∑
3985:−
3964:−
3937:−
3916:−
3910:−
3714:∖
3701:∈
3692:⌋
3680:−
3671:⌊
3590:∖
3533:⌋
3521:−
3512:⌊
3470:Θ
3447:−
3398:Θ
3387:−
3370:−
3355:−
3331:−
3320:−
3300:−
3282:∑
3272:−
3257:−
3219:−
3208:−
3187:−
3172:−
3145:−
3124:−
3118:−
2995:−
2989:−
2957:…
2894:−
2793:…
2665:Θ
2591:Θ
2559:Θ
2513:Θ
2384:−
2283:≤
2277:≤
2236:…
2215:−
2206:…
2103:≤
2097:≤
1640:…
1610:−
1596:…
1558:∖
1519:≤
1513:≤
1454:…
1368:→
1362:→
1356:→
1350:→
1344:→
1278:→
1168:→
1162:→
1156:→
1150:→
993:→
987:→
981:→
975:→
949:→
943:→
937:→
931:→
905:→
899:→
893:→
887:→
861:→
855:→
849:→
823:→
817:→
811:→
742:→
736:→
730:→
704:→
698:→
692:→
619:→
613:→
505:∅
173:≠
141:…
129:⊆
79:…
4814:9. 1962.
4671:function
4667:Source:
4603:⌋
4590:⌊
4295:of size
3738:, where
2477:through
2373:to give
2318:to city
1936:through
1849:through
1735:through
1534:, write
1333:must be
1203:through
1081:through
4724:end for
4721:end for
4718:end for
4715:m≠k,m∈S
4707:for all
4700:for all
4686:end for
4231:bitmask
3765:is the
876:, then
97:, with
33:Bellman
27:, is a
4766:et al.
4733:(opt)
4731:return
4709:k ∈ S
4509:where
4275:for a
3065:where
2736:for a
2060:, and
561:, and
4848:(PDF)
4841:(PDF)
4616:, to
3837:Space
1695:from
760:Once
436:When
47:, in
4753:and
4695:n−1
3494:For
2697:Time
1775:has
37:Karp
19:The
4794:).
4728:k≠1
4689:for
4678:for
4555:or
3769:of
2776:of
2457:to
2090:min
1916:to
1822:to
1755:to
1313:to
1247:to
1139:is
1119:to
719:or
358:to
228:to
4864::
4711:do
4704:do
4697:do
4693:to
4682:do
4675:is
4659:.
2180:.
51:.
4647:)
4642:n
4638:2
4632:n
4627:(
4598:2
4595:n
4586:=
4583:k
4563:k
4543:1
4537:k
4517:S
4497:)
4494:e
4491:,
4488:S
4485:(
4482:g
4461:]
4454:)
4449:k
4445:2
4439:n
4433:(
4427:+
4421:)
4415:1
4409:k
4404:2
4398:n
4392:(
4385:[
4381:)
4378:1
4372:n
4369:(
4349:1
4343:k
4323:g
4303:k
4283:S
4263:)
4260:e
4257:,
4254:S
4251:(
4248:g
4217:S
4197:n
4177:)
4172:n
4168:2
4164:n
4161:(
4155:=
4150:n
4146:2
4142:)
4139:1
4133:n
4130:(
4127:=
4121:)
4116:k
4112:2
4106:n
4100:(
4094:)
4091:1
4085:n
4082:(
4077:2
4071:n
4066:0
4063:=
4060:k
4035:)
4032:e
4029:,
4026:S
4023:(
4020:g
3997:)
3992:k
3988:2
3982:n
3976:(
3970:)
3967:1
3961:n
3958:(
3955:=
3949:)
3944:k
3940:1
3934:n
3928:(
3922:)
3919:1
3913:k
3907:n
3904:(
3884:k
3864:)
3861:e
3858:,
3855:S
3852:(
3849:g
3821:e
3801:1
3777:S
3751:c
3747:S
3726:}
3723:}
3720:1
3717:{
3709:c
3705:S
3698:e
3695:,
3687:2
3683:1
3677:n
3668:=
3664:|
3660:S
3656:|
3652::
3649:)
3646:e
3643:,
3640:S
3637:(
3634:{
3614:)
3611:e
3608:,
3605:}
3602:e
3599:,
3596:1
3593:{
3585:c
3581:S
3577:(
3574:g
3571:+
3568:)
3565:e
3562:,
3559:S
3556:(
3553:g
3528:2
3524:1
3518:n
3509:=
3506:k
3479:)
3476:n
3473:(
3450:1
3444:n
3424:)
3419:n
3415:2
3409:2
3405:n
3401:(
3395:=
3390:3
3384:n
3380:2
3376:)
3373:2
3367:n
3364:(
3361:)
3358:1
3352:n
3349:(
3346:=
3340:)
3334:1
3328:k
3323:3
3317:n
3311:(
3303:2
3297:n
3292:1
3289:=
3286:k
3278:)
3275:2
3269:n
3266:(
3263:)
3260:1
3254:n
3251:(
3228:)
3222:1
3216:k
3211:3
3205:n
3199:(
3193:)
3190:2
3184:n
3181:(
3178:)
3175:1
3169:n
3166:(
3163:=
3157:)
3152:k
3148:1
3142:n
3136:(
3130:)
3127:1
3121:k
3115:n
3112:(
3109:k
3089:k
3086:=
3082:|
3078:S
3074:|
3053:)
3050:e
3047:,
3044:S
3041:(
3038:g
3018:e
2998:1
2992:k
2986:n
2966:}
2963:n
2960:,
2954:,
2951:2
2948:{
2928:k
2906:)
2901:k
2897:1
2891:n
2885:(
2862:k
2842:g
2822:k
2802:}
2799:n
2796:,
2790:,
2787:2
2784:{
2764:S
2744:k
2724:)
2721:e
2718:,
2715:S
2712:(
2709:g
2681:)
2676:2
2672:n
2668:(
2645:)
2642:e
2639:,
2636:S
2633:(
2630:g
2610:)
2605:n
2601:2
2597:n
2594:(
2571:)
2568:!
2565:n
2562:(
2539:)
2534:2
2530:n
2524:n
2520:2
2516:(
2485:S
2465:e
2445:1
2425:)
2422:e
2419:,
2416:S
2413:(
2410:g
2387:1
2381:n
2361:)
2358:1
2355:,
2352:i
2349:(
2346:d
2326:i
2306:1
2286:n
2280:i
2274:2
2254:)
2251:i
2248:,
2245:}
2242:n
2239:,
2233:,
2230:1
2227:+
2224:i
2221:,
2218:1
2212:i
2209:,
2203:,
2200:2
2197:{
2194:(
2191:g
2168:)
2165:e
2162:,
2157:i
2153:s
2149:(
2146:d
2143:+
2140:)
2135:i
2131:s
2127:,
2122:i
2118:S
2114:(
2111:g
2106:k
2100:i
2094:1
2086:=
2083:)
2080:e
2077:,
2074:S
2071:(
2068:g
2048:)
2045:e
2042:,
2037:i
2033:s
2029:(
2026:d
2023:+
2020:)
2015:i
2011:s
2007:,
2002:i
1998:S
1994:(
1991:g
1969:i
1965:s
1944:S
1924:e
1904:1
1884:k
1862:i
1858:S
1835:i
1831:s
1810:1
1788:i
1784:s
1763:e
1743:S
1723:1
1703:S
1681:i
1677:s
1656:}
1651:k
1647:s
1643:,
1637:,
1632:1
1629:+
1626:i
1622:s
1618:,
1613:1
1607:i
1603:s
1599:,
1593:,
1588:1
1584:s
1580:{
1577:=
1574:}
1569:i
1565:s
1561:{
1555:S
1552:=
1547:i
1543:S
1522:k
1516:i
1510:1
1490:k
1470:}
1465:k
1461:s
1457:,
1451:,
1446:1
1442:s
1438:{
1435:=
1432:S
1409:}
1406:4
1403:,
1400:3
1397:,
1394:2
1391:{
1371:6
1365:5
1359:2
1353:3
1347:4
1341:1
1321:6
1301:1
1281:6
1275:5
1255:6
1235:}
1232:5
1229:,
1226:4
1223:,
1220:3
1217:,
1214:2
1211:{
1191:1
1171:5
1165:2
1159:3
1153:4
1147:1
1127:5
1107:}
1104:4
1101:,
1098:3
1095:,
1092:2
1089:{
1069:1
1049:)
1046:5
1043:,
1040:}
1037:4
1034:,
1031:3
1028:,
1025:2
1022:{
1019:(
1016:g
996:5
990:4
984:2
978:3
972:1
952:5
946:4
940:2
934:3
928:1
908:5
902:4
896:3
890:2
884:1
864:4
858:2
852:3
846:1
826:4
820:3
814:2
808:1
788:S
768:S
745:4
739:2
733:3
727:1
707:4
701:3
695:2
689:1
669:)
666:4
663:,
660:}
657:3
654:,
651:2
648:{
645:(
642:g
622:3
616:2
610:1
590:)
587:3
584:,
581:}
578:2
575:{
572:(
569:g
549:)
546:e
543:,
540:1
537:(
534:d
514:)
511:e
508:,
502:(
499:g
479:)
476:e
473:,
470:S
467:(
464:g
444:S
421:S
401:)
398:e
395:,
392:S
389:(
386:g
366:v
346:u
326:)
323:v
320:,
317:u
314:(
311:d
291:)
288:e
285:,
282:S
279:(
276:g
256:S
236:e
216:1
196:S
176:1
170:e
150:}
147:n
144:,
138:,
135:2
132:{
126:S
105:1
85:n
82:,
76:,
73:2
70:,
67:1
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.