2137:
31:
1029:
485:
759:. In computer science, interesting optimization problems usually have the above properties and are therefore NPO problems. A problem is additionally called a P-optimization (PO) problem, if there exists an algorithm which finds optimal solutions in polynomial time. Often, when dealing with the class NPO, one is interested in optimization problems for which the decision versions are
470:
deals with algorithms to find near-optimal solutions to hard problems. The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions. Even though we could introduce suitable decision problems, the problem is then more naturally characterized
763:. Note that hardness relations are always with respect to some reduction. Due to the connection between approximation algorithms and computational optimization problems, reductions which preserve approximation in some respect are for this subject preferred than the usual
863:: The class of NPO problems with polynomial-time algorithms approximating the optimal solution by a ratio that is polynomial in a logarithm of the size of the input. In HromkoviÄŤ's book, all NPO(III)-problems are excluded from this class unless P=NP. Contains the
873:: The class of NPO problems with polynomial-time algorithms approximating the optimal solution by a ratio bounded by some function on n. In Hromkovic's book, all NPO(IV)-problems are excluded from this class unless P=NP. Contains the
278:(a greedy-type swapping algorithm). However, generic search algorithms are not guaranteed to find an optimal solution first, nor are they guaranteed to run quickly (in polynomial time). Since some discrete optimization problems are
250:
solving real-world instances that arise in practice and do not necessarily exhibit the worst-case behavior of in NP-complete problems (e.g. real-world TSP instances with tens of thousands of nodes).
1460:
Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does not matter in which direction in time they come after each other: 14!/2 = 43,589,145,600.
715:
652:
1251:
942:
583:
977:
318:
843:
997:
907:
745:
607:
461:
441:
421:
401:
381:
361:
341:
2034:
81:
is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.
228:
254:
Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items; therefore, in principle, any sort of
1905:
1785:
1322:
2029:
1203:
423:
that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from
1087:
1018:
17:
2630:
2523:
2043:
2635:
1898:
1841:
1818:
1797:
1578:
1422:
1395:
240:
1362:
800:
1228:
2625:
2604:
2066:
1008:
2118:
1979:
1014:
2086:
1735:
1712:
1687:
1661:
1505:
1446:
849:'s book, excluded from this class are all NPO(II)-problems save if P=NP. Without the exclusion, equals APX. Contains
775:. For this reason, optimization problems with NP-complete decision versions are not necessarily called NPO-complete.
657:
546:
are functions of the size of the respective functions' inputs, not the size of some implicit set of input instances.
542:(NPO) is a combinatorial optimization problem with the following additional conditions. Note that the below referred
525:
2197:
1891:
1127:
1036:’s 15 largest cities. It is the shortest among the 43,589,145,600 possible tours that visit each city exactly once.
2136:
1056:
507:
93:
2474:
1275:
Hobé, Alex; Vogler, Daniel; Seybold, Martin P.; Ebigbo, Anozie; Settgast, Randolph R.; Saar, Martin O. (2018).
813:: The class of NPO problems that have polynomial-time algorithms which computes solutions with a cost at most
615:
181:
for certain special classes of discrete optimization. A considerable amount of it is unified by the theory of
2582:
2202:
2518:
2486:
1117:
321:
244:
121:
1276:
2567:
2192:
1590:
Das, Arnab; Chakrabarti, Bikas K (2008). "Colloquium: Quantum annealing and analog quantum computation".
874:
854:
66:
2513:
2469:
2091:
2071:
1139:
1112:
1022:
500:. In particular, the notation introduced in this section is not explained well and may not be standard.
2281:
2252:
1914:
221:
178:
141:
50:
2437:
1883:
1622:
2299:
1097:
503:
1172:
2481:
2380:
2096:
1673:
1550:(This is a continuously updated catalog of approximability results for NP optimization problems.)
1122:
467:
234:
202:
97:
2572:
2557:
2447:
2325:
1974:
1951:
1918:
1617:
1522:
1489:
912:
553:
185:. Some examples of combinatorial optimization problems that are covered by this framework are
2461:
2427:
2330:
2272:
2153:
1959:
1939:
1092:
1061:
70:
35:
947:
2508:
2335:
2247:
1609:
1566:
1540:
1298:
296:
216:
discrete optimization problems, current research literature includes the following topics:
109:
42:. Finding a minimum spanning tree is a common problem involving combinatorial optimization.
8:
2577:
2442:
2395:
2385:
2237:
2225:
2038:
2021:
1926:
1558:
1493:
1077:
1072:
1046:
820:
495:
271:
117:
85:
65:
or can be reduced to a discrete set. Typical combinatorial optimization problems are the
1613:
1570:
1302:
1277:"Estimating fluid flow rates through fracture networks using combinatorial optimization"
1017:
and may never be able to satisfy particular standards for completeness. You can help by
463:
that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.
2312:
2267:
2257:
2048:
1964:
1635:
1599:
1314:
1288:
1195:
1041:
982:
892:
730:
718:
592:
446:
426:
406:
386:
366:
346:
326:
190:
182:
58:
846:
266:(an exact algorithm which can be stopped at any point in time to serve as heuristic),
2320:
1998:
1873:
1857:
1837:
1814:
1793:
1731:
1708:
1700:
1683:
1657:
1574:
1501:
1475:
1442:
1418:
1391:
1318:
1199:
1107:
1102:
78:
1639:
1310:
2400:
2390:
2294:
2171:
2076:
2058:
2011:
1922:
1627:
1306:
1243:
1187:
1082:
790:
764:
290:
263:
255:
101:
74:
1878:
2416:
1831:
1725:
1677:
1544:
1536:
1485:
1051:
778:
NPO is divided into the following subclasses according to their approximability:
760:
756:
748:
722:
1748:
1355:
1247:
2404:
2289:
2176:
2110:
2081:
1631:
1518:
1066:
878:
768:
267:
105:
1770:
1191:
999:. The class NPOPB is the class of NPO problems that are polynomially-bounded.
2619:
2562:
2546:
1649:
282:, such as the traveling salesman (decision) problem, this is expected unless
259:
198:
186:
161:
220:
polynomial-time exactly solvable special cases of the problem at hand (e.g.
132:
Applications of combinatorial optimization include, but are not limited to:
2500:
2006:
1755:
293:
that asks whether there is a feasible solution for some particular measure
194:
62:
39:
1229:"Sustainable supply chain network design: An optimization-oriented review"
1227:
Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; PĂ©ton, Olivier (2015).
2587:
1969:
1833:
Advances in Bio-inspired
Computing for Combinatorial Optimization Problem
772:
586:
279:
275:
213:
1867:
237:
that run in polynomial time and find a solution that is close to optimal
30:
1790:
Networks in Action; Text and
Computer Exercises in Network Optimization
543:
54:
817:
times the optimal cost (for minimization problems) or a cost at least
289:
For each combinatorial optimization problem, there is a corresponding
1913:
864:
165:
136:
89:
1028:
1989:
1293:
804:
274:(a recursive solution construction with limited search window) and
1604:
1484:
1417:, Texts in Theoretical Computer Science (2nd ed.), Springer,
2309:
1862:
1033:
850:
227:
algorithms that perform well on "random" instances (e.g. for the
206:
262:
can be used to solve them. Widely applicable approaches include
77:. In many such problems, such as the ones previously mentioned,
1226:
146:
Developing the best airline network of spokes and destinations
1534:
786:
283:
96:. It has important applications in several fields, including
1879:
Complexity classes for optimization problems / Stefan Kugele
1705:
1439:
755:
This implies that the corresponding decision problem is in
113:
1749:"On the history of combinatorial optimization (till 1960)"
1528:(Information on the largest TSP instances solved to date.)
1808:
149:
Deciding which taxis in a fleet to route to pick up fares
1730:. Algorithms and Combinatorics. Vol. 24. Springer.
1535:
Crescenzi, Pierluigi; Kann, Viggo; HalldĂłrsson, MagnĂşs;
1274:
1698:
1565:. Lecture Notes in Physics. Vol. 679. Springer.
985:
950:
915:
895:
823:
733:
660:
618:
595:
556:
449:
429:
409:
389:
383:, an optimization problem might be "find a path from
369:
349:
329:
299:
2426:
1811:
Linear and
Integer Optimization: Theory and Practice
1727:
845:
of the optimal cost (for maximization problems). In
1836:. Intelligent Systems Reference Library. Springer.
979:is bounded by a polynomial function of the size of
1563:Quantum Annealing and Related Optimization Methods
991:
971:
936:
901:
837:
739:
709:
646:
601:
577:
455:
435:
415:
395:
375:
355:
335:
312:
53:that consists of finding an optimal object from a
1654:Combinatorial Optimization: Networks and Matroids
2617:
1173:"Combinatorial optimization and Green Logistics"
1863:The Aussois Combinatorial Optimization Workshop
710:{\displaystyle \{\,(x,y)\,\mid \,y\in f(x)\,\}}
270:(uses linear optimisation to generate bounds),
152:Determining the optimal way to deliver packages
1589:
1556:
1171:Sbihi, Abdelkader; Eglese, Richard W. (2007).
1032:An optimal traveling salesperson tour through
1899:
1784:
1408:
1406:
247:time and find a solution close to the optimum
2460:
1679:A First Course in Combinatorial Optimization
704:
661:
641:
619:
506:. There might be a discussion about this on
1938:
1170:
1088:Minimum relevant variables in linear system
1906:
1892:
1758:; Nemhauser, G.L.; Weismantel, R. (eds.).
1545:"A Compendium of NP Optimization Problems"
1403:
771:. An example of such a reduction would be
474:
2152:
1769:Schrijver, Alexander (February 1, 2006).
1768:
1746:
1723:
1621:
1603:
1441:, Royal Institute of Technology, Sweden,
1412:
1379:
1292:
1158:
703:
684:
680:
664:
640:
630:
626:
622:
526:Learn how and when to remove this message
177:There is a large amount of literature on
84:Combinatorial optimization is related to
2140:Optimization computes maxima and minima.
1868:Java Combinatorial Optimization Platform
1385:
1027:
647:{\displaystyle \{\,x\,\mid \,x\in I\,\}}
29:
2224:
1386:Ausiello, Giorgio; et al. (2003),
14:
2618:
1829:
1772:A Course in Combinatorial Optimization
1648:
241:parameterized approximation algorithms
2544:
2360:
2336:Principal pivoting algorithm of Lemke
2223:
2151:
1937:
1887:
1858:Journal of Combinatorial Optimization
1430:
158:Designing water distribution networks
27:Subfield of mathematical optimization
1809:Gerard Sierksma; Yori Zwols (2015).
1516:
1436:
1342:
1002:
550:the size of every feasible solution
478:
1672:
1473:
1009:Category:Combinatorial optimization
155:Allocating jobs to people optimally
24:
2545:
2135:
1980:Successive parabolic interpolation
589:in the size of the given instance
25:
2647:
2361:
2300:Projective algorithm of Karmarkar
1851:
1760:Handbook of Discrete Optimization
2295:Ellipsoid algorithm of Khachiyan
2198:Sequential quadratic programming
2035:Broyden–Fletcher–Goldfarb–Shanno
1390:(Corrected ed.), Springer,
1128:Weapon target assignment problem
483:
2631:Computational complexity theory
1454:
1368:from the original on 2022-03-01
1325:from the original on 2020-08-21
1311:10.1016/j.advwatres.2018.10.002
1257:from the original on 2019-12-26
1209:from the original on 2019-12-26
1057:Constraint satisfaction problem
127:
94:computational complexity theory
2253:Reduced gradient (Frank–Wolfe)
1874:Why is scheduling people hard?
1682:. Cambridge University Press.
1415:Algorithmics for Hard Problems
1348:
1336:
1268:
1220:
1164:
1152:
966:
954:
931:
925:
700:
694:
677:
665:
572:
566:
13:
1:
2583:Spiral optimization algorithm
2203:Successive linear programming
1747:Schrijver, Alexander (2005).
1724:Schrijver, Alexander (2003).
1467:
320:. For example, if there is a
71:minimum spanning tree problem
57:of objects, where the set of
2636:Theoretical computer science
2321:Simplex algorithm of Dantzig
2193:Augmented Lagrangian methods
1699:Papadimitriou, Christos H.;
1388:Complexity and Approximation
1118:Vehicle rescheduling problem
889:(PB) if, for every instance
471:as an optimization problem.
122:theoretical computer science
7:
1281:Advances in Water Resources
1248:10.1016/j.omega.2015.01.006
1133:
67:travelling salesman problem
10:
2652:
2626:Combinatorial optimization
1762:. Elsevier. pp. 1–68.
1632:10.1103/RevModPhys.80.1061
1498:Combinatorial Optimization
1488:; Cunningham, William H.;
1140:Constraint composite graph
1113:Traveling salesman problem
1012:
1006:
749:polynomial-time computable
229:traveling salesman problem
179:polynomial-time algorithms
172:
47:Combinatorial optimization
18:Combinatorial Optimization
2600:
2553:
2540:
2524:Push–relabel maximum flow
2499:
2415:
2373:
2369:
2356:
2326:Revised simplex algorithm
2308:
2280:
2266:
2236:
2232:
2219:
2185:
2164:
2160:
2147:
2133:
2109:
2057:
2020:
1997:
1988:
1950:
1946:
1933:
1788:; Ghosh, Diptesh (2010).
1413:Hromkovic, Juraj (2002),
1192:10.1007/s10288-007-0047-3
937:{\displaystyle y\in f(x)}
885:An NPO problem is called
578:{\displaystyle y\in f(x)}
222:fixed-parameter tractable
142:Supply chain optimization
51:mathematical optimization
2049:Symmetric rank-one (SR1)
2030:Berndt–Hall–Hall–Hausman
1145:
1098:Nurse scheduling problem
468:approximation algorithms
343:which contains vertices
235:approximation algorithms
2573:Parallel metaheuristics
2381:Approximation algorithm
2092:Powell's dog leg method
2044:Davidon–Fletcher–Powell
1940:Unconstrained nonlinear
1490:Pulleyblank, William R.
1123:Vehicle routing problem
909:and for every solution
540:NP-optimization problem
475:NP optimization problem
98:artificial intelligence
2558:Evolutionary algorithm
2141:
1523:University of Waterloo
1517:Cook, William (2016).
1037:
993:
973:
972:{\displaystyle m(x,y)}
938:
903:
839:
741:
711:
648:
603:
579:
457:
437:
417:
397:
377:
357:
337:
314:
195:flows and circulations
43:
2331:Criss-cross algorithm
2154:Constrained nonlinear
2139:
1960:Golden-section search
1830:Pintea, C-M. (2014).
1476:"Integer programming"
1093:Minimum spanning tree
1062:Cutting stock problem
1031:
1007:Further information:
994:
974:
939:
904:
840:
742:
712:
649:
604:
580:
458:
438:
418:
398:
378:
358:
338:
315:
313:{\displaystyle m_{0}}
36:minimum spanning tree
33:
2248:Cutting-plane method
1559:Chakrabarti, Bikas K
1494:Schrijver, Alexander
1437:Kann, Viggo (1992),
1019:adding missing items
983:
948:
913:
893:
887:polynomially bounded
821:
731:
658:
616:
593:
554:
496:confusing or unclear
447:
427:
407:
387:
367:
347:
327:
297:
110:software engineering
2578:Simulated annealing
2396:Integer programming
2386:Dynamic programming
2226:Convex optimization
2087:Levenberg–Marquardt
1614:2008RvMP...80.1061D
1571:2005qnro.book.....D
1519:"Optimal TSP Tours"
1356:"Approximation-TSP"
1303:2018AdWR..122...85H
1078:Job shop scheduling
1073:Integer programming
1047:Bin packing problem
838:{\displaystyle 1/c}
807:scheduling problem.
504:clarify the section
272:dynamic programming
191:shortest-path trees
118:applied mathematics
86:operations research
2258:Subgradient method
2142:
2067:Conjugate gradient
1975:Nelder–Mead method
1870:(open source code)
1701:Steiglitz, Kenneth
1541:Woeginger, Gerhard
1042:Assignment problem
1038:
989:
969:
934:
899:
835:
737:
707:
644:
599:
575:
453:
433:
413:
393:
373:
353:
333:
310:
183:linear programming
59:feasible solutions
44:
2613:
2612:
2596:
2595:
2536:
2535:
2532:
2531:
2495:
2494:
2456:
2455:
2352:
2351:
2348:
2347:
2344:
2343:
2215:
2214:
2211:
2210:
2131:
2130:
2127:
2126:
2105:
2104:
1843:978-3-642-40178-7
1820:978-1-498-71016-9
1799:978-1-4419-5512-8
1580:978-3-540-27987-7
1424:978-3-540-44134-2
1397:978-3-540-65431-5
1108:Talent Scheduling
1103:Set cover problem
1003:Specific problems
992:{\displaystyle x}
902:{\displaystyle x}
740:{\displaystyle m}
602:{\displaystyle x}
536:
535:
528:
456:{\displaystyle v}
436:{\displaystyle u}
416:{\displaystyle v}
396:{\displaystyle u}
376:{\displaystyle v}
356:{\displaystyle u}
336:{\displaystyle G}
79:exhaustive search
73:("MST"), and the
49:is a subfield of
16:(Redirected from
2643:
2542:
2541:
2458:
2457:
2424:
2423:
2401:Branch and bound
2391:Greedy algorithm
2371:
2370:
2358:
2357:
2278:
2277:
2234:
2233:
2221:
2220:
2162:
2161:
2149:
2148:
2097:Truncated Newton
2012:Wolfe conditions
1995:
1994:
1948:
1947:
1935:
1934:
1908:
1901:
1894:
1885:
1884:
1847:
1824:
1803:
1786:Sierksma, Gerard
1779:
1777:
1763:
1753:
1741:
1718:
1693:
1667:
1643:
1625:
1607:
1584:
1548:
1537:Karpinski, Marek
1526:
1511:
1486:Cook, William J.
1479:
1478:(lecture notes).
1461:
1458:
1452:
1451:
1434:
1428:
1427:
1410:
1401:
1400:
1383:
1377:
1376:
1374:
1373:
1367:
1360:
1352:
1346:
1340:
1334:
1333:
1331:
1330:
1296:
1272:
1266:
1265:
1263:
1262:
1256:
1233:
1224:
1218:
1217:
1215:
1214:
1208:
1177:
1168:
1162:
1156:
1083:Knapsack problem
1023:reliable sources
998:
996:
995:
990:
978:
976:
975:
970:
943:
941:
940:
935:
908:
906:
905:
900:
844:
842:
841:
836:
831:
791:Knapsack problem
746:
744:
743:
738:
716:
714:
713:
708:
653:
651:
650:
645:
608:
606:
605:
600:
585:is polynomially
584:
582:
581:
576:
531:
524:
520:
517:
511:
487:
486:
479:
462:
460:
459:
454:
442:
440:
439:
434:
422:
420:
419:
414:
402:
400:
399:
394:
382:
380:
379:
374:
362:
360:
359:
354:
342:
340:
339:
334:
319:
317:
316:
311:
309:
308:
291:decision problem
264:branch-and-bound
256:search algorithm
102:machine learning
90:algorithm theory
75:knapsack problem
21:
2651:
2650:
2646:
2645:
2644:
2642:
2641:
2640:
2616:
2615:
2614:
2609:
2592:
2549:
2528:
2491:
2452:
2429:
2418:
2411:
2365:
2340:
2304:
2271:
2262:
2239:
2228:
2207:
2181:
2177:Penalty methods
2172:Barrier methods
2156:
2143:
2123:
2119:Newton's method
2101:
2053:
2016:
1984:
1965:Powell's method
1942:
1929:
1912:
1854:
1844:
1821:
1800:
1775:
1751:
1738:
1715:
1690:
1664:
1623:10.1.1.563.9990
1581:
1561:, eds. (2005).
1508:
1474:Beasley, J. E.
1470:
1465:
1464:
1459:
1455:
1449:
1435:
1431:
1425:
1411:
1404:
1398:
1384:
1380:
1371:
1369:
1365:
1358:
1354:
1353:
1349:
1341:
1337:
1328:
1326:
1273:
1269:
1260:
1258:
1254:
1231:
1225:
1221:
1212:
1210:
1206:
1175:
1169:
1165:
1157:
1153:
1148:
1136:
1052:Closure problem
1026:
1011:
1005:
984:
981:
980:
949:
946:
945:
914:
911:
910:
894:
891:
890:
827:
822:
819:
818:
803:. Contains the
789:. Contains the
769:Karp reductions
732:
729:
728:
723:polynomial time
659:
656:
655:
617:
614:
613:
594:
591:
590:
555:
552:
551:
532:
521:
515:
512:
501:
488:
484:
477:
448:
445:
444:
428:
425:
424:
408:
405:
404:
388:
385:
384:
368:
365:
364:
348:
345:
344:
328:
325:
324:
304:
300:
298:
295:
294:
175:
164:problems (e.g.
130:
28:
23:
22:
15:
12:
11:
5:
2649:
2639:
2638:
2633:
2628:
2611:
2610:
2608:
2607:
2601:
2598:
2597:
2594:
2593:
2591:
2590:
2585:
2580:
2575:
2570:
2565:
2560:
2554:
2551:
2550:
2547:Metaheuristics
2538:
2537:
2534:
2533:
2530:
2529:
2527:
2526:
2521:
2519:Ford–Fulkerson
2516:
2511:
2505:
2503:
2497:
2496:
2493:
2492:
2490:
2489:
2487:Floyd–Warshall
2484:
2479:
2478:
2477:
2466:
2464:
2454:
2453:
2451:
2450:
2445:
2440:
2434:
2432:
2421:
2413:
2412:
2410:
2409:
2408:
2407:
2393:
2388:
2383:
2377:
2375:
2367:
2366:
2354:
2353:
2350:
2349:
2346:
2345:
2342:
2341:
2339:
2338:
2333:
2328:
2323:
2317:
2315:
2306:
2305:
2303:
2302:
2297:
2292:
2290:Affine scaling
2286:
2284:
2282:Interior point
2275:
2264:
2263:
2261:
2260:
2255:
2250:
2244:
2242:
2230:
2229:
2217:
2216:
2213:
2212:
2209:
2208:
2206:
2205:
2200:
2195:
2189:
2187:
2186:Differentiable
2183:
2182:
2180:
2179:
2174:
2168:
2166:
2158:
2157:
2145:
2144:
2134:
2132:
2129:
2128:
2125:
2124:
2122:
2121:
2115:
2113:
2107:
2106:
2103:
2102:
2100:
2099:
2094:
2089:
2084:
2079:
2074:
2069:
2063:
2061:
2055:
2054:
2052:
2051:
2046:
2041:
2032:
2026:
2024:
2018:
2017:
2015:
2014:
2009:
2003:
2001:
1992:
1986:
1985:
1983:
1982:
1977:
1972:
1967:
1962:
1956:
1954:
1944:
1943:
1931:
1930:
1911:
1910:
1903:
1896:
1888:
1882:
1881:
1876:
1871:
1865:
1860:
1853:
1852:External links
1850:
1849:
1848:
1842:
1826:
1825:
1819:
1805:
1804:
1798:
1781:
1780:
1765:
1764:
1743:
1742:
1736:
1720:
1719:
1713:
1695:
1694:
1688:
1669:
1668:
1662:
1650:Lawler, Eugene
1645:
1644:
1592:Rev. Mod. Phys
1586:
1585:
1579:
1553:
1552:
1531:
1530:
1513:
1512:
1506:
1481:
1480:
1469:
1466:
1463:
1462:
1453:
1447:
1429:
1423:
1402:
1396:
1378:
1347:
1335:
1267:
1219:
1163:
1159:Schrijver 2003
1150:
1149:
1147:
1144:
1143:
1142:
1135:
1132:
1131:
1130:
1125:
1120:
1115:
1110:
1105:
1100:
1095:
1090:
1085:
1080:
1075:
1070:
1067:Dominating set
1064:
1059:
1054:
1049:
1044:
1004:
1001:
988:
968:
965:
962:
959:
956:
953:
944:, the measure
933:
930:
927:
924:
921:
918:
898:
883:
882:
879:clique problem
868:
858:
834:
830:
826:
808:
794:
753:
752:
736:
726:
706:
702:
699:
696:
693:
690:
687:
683:
679:
676:
673:
670:
667:
663:
643:
639:
636:
633:
629:
625:
621:
612:the languages
610:
598:
574:
571:
568:
565:
562:
559:
534:
533:
491:
489:
482:
476:
473:
452:
432:
412:
392:
372:
352:
332:
307:
303:
268:branch-and-cut
252:
251:
248:
238:
232:
225:
199:spanning trees
187:shortest paths
174:
171:
170:
169:
159:
156:
153:
150:
147:
144:
139:
129:
126:
106:auction theory
38:of a weighted
26:
9:
6:
4:
3:
2:
2648:
2637:
2634:
2632:
2629:
2627:
2624:
2623:
2621:
2606:
2603:
2602:
2599:
2589:
2586:
2584:
2581:
2579:
2576:
2574:
2571:
2569:
2566:
2564:
2563:Hill climbing
2561:
2559:
2556:
2555:
2552:
2548:
2543:
2539:
2525:
2522:
2520:
2517:
2515:
2512:
2510:
2507:
2506:
2504:
2502:
2501:Network flows
2498:
2488:
2485:
2483:
2480:
2476:
2473:
2472:
2471:
2468:
2467:
2465:
2463:
2462:Shortest path
2459:
2449:
2446:
2444:
2441:
2439:
2436:
2435:
2433:
2431:
2430:spanning tree
2425:
2422:
2420:
2414:
2406:
2402:
2399:
2398:
2397:
2394:
2392:
2389:
2387:
2384:
2382:
2379:
2378:
2376:
2372:
2368:
2364:
2363:Combinatorial
2359:
2355:
2337:
2334:
2332:
2329:
2327:
2324:
2322:
2319:
2318:
2316:
2314:
2311:
2307:
2301:
2298:
2296:
2293:
2291:
2288:
2287:
2285:
2283:
2279:
2276:
2274:
2269:
2265:
2259:
2256:
2254:
2251:
2249:
2246:
2245:
2243:
2241:
2235:
2231:
2227:
2222:
2218:
2204:
2201:
2199:
2196:
2194:
2191:
2190:
2188:
2184:
2178:
2175:
2173:
2170:
2169:
2167:
2163:
2159:
2155:
2150:
2146:
2138:
2120:
2117:
2116:
2114:
2112:
2108:
2098:
2095:
2093:
2090:
2088:
2085:
2083:
2080:
2078:
2075:
2073:
2070:
2068:
2065:
2064:
2062:
2060:
2059:Other methods
2056:
2050:
2047:
2045:
2042:
2040:
2036:
2033:
2031:
2028:
2027:
2025:
2023:
2019:
2013:
2010:
2008:
2005:
2004:
2002:
2000:
1996:
1993:
1991:
1987:
1981:
1978:
1976:
1973:
1971:
1968:
1966:
1963:
1961:
1958:
1957:
1955:
1953:
1949:
1945:
1941:
1936:
1932:
1928:
1924:
1920:
1916:
1909:
1904:
1902:
1897:
1895:
1890:
1889:
1886:
1880:
1877:
1875:
1872:
1869:
1866:
1864:
1861:
1859:
1856:
1855:
1845:
1839:
1835:
1834:
1828:
1827:
1822:
1816:
1813:. CRC Press.
1812:
1807:
1806:
1801:
1795:
1791:
1787:
1783:
1782:
1774:
1773:
1767:
1766:
1761:
1757:
1750:
1745:
1744:
1739:
1737:9783540443896
1733:
1729:
1728:
1722:
1721:
1716:
1714:0-486-40258-4
1710:
1706:
1703:(July 1998).
1702:
1697:
1696:
1691:
1689:0-521-01012-8
1685:
1681:
1680:
1675:
1671:
1670:
1665:
1663:0-486-41453-1
1659:
1655:
1651:
1647:
1646:
1641:
1637:
1633:
1629:
1624:
1619:
1615:
1611:
1606:
1601:
1597:
1593:
1588:
1587:
1582:
1576:
1572:
1568:
1564:
1560:
1555:
1554:
1551:
1546:
1542:
1538:
1533:
1532:
1529:
1524:
1520:
1515:
1514:
1509:
1507:0-471-55894-X
1503:
1499:
1495:
1491:
1487:
1483:
1482:
1477:
1472:
1471:
1457:
1450:
1448:91-7170-082-X
1444:
1440:
1433:
1426:
1420:
1416:
1409:
1407:
1399:
1393:
1389:
1382:
1364:
1357:
1351:
1344:
1339:
1324:
1320:
1316:
1312:
1308:
1304:
1300:
1295:
1290:
1286:
1282:
1278:
1271:
1253:
1249:
1245:
1241:
1237:
1230:
1223:
1205:
1201:
1197:
1193:
1189:
1186:(2): 99–116.
1185:
1181:
1174:
1167:
1160:
1155:
1151:
1141:
1138:
1137:
1129:
1126:
1124:
1121:
1119:
1116:
1114:
1111:
1109:
1106:
1104:
1101:
1099:
1096:
1094:
1091:
1089:
1086:
1084:
1081:
1079:
1076:
1074:
1071:
1068:
1065:
1063:
1060:
1058:
1055:
1053:
1050:
1048:
1045:
1043:
1040:
1039:
1035:
1030:
1024:
1020:
1016:
1010:
1000:
986:
963:
960:
957:
951:
928:
922:
919:
916:
896:
888:
880:
876:
872:
869:
866:
862:
859:
856:
852:
848:
832:
828:
824:
816:
812:
809:
806:
802:
798:
795:
792:
788:
784:
781:
780:
779:
776:
774:
770:
766:
762:
758:
750:
734:
727:
724:
720:
697:
691:
688:
685:
681:
674:
671:
668:
637:
634:
631:
627:
623:
611:
596:
588:
569:
563:
560:
557:
549:
548:
547:
545:
541:
530:
527:
519:
516:December 2021
509:
508:the talk page
505:
499:
497:
492:This section
490:
481:
480:
472:
469:
466:The field of
464:
450:
430:
410:
390:
370:
350:
330:
323:
305:
301:
292:
287:
285:
281:
277:
273:
269:
265:
261:
260:metaheuristic
257:
249:
246:
242:
239:
236:
233:
230:
226:
223:
219:
218:
217:
215:
210:
208:
204:
200:
196:
192:
188:
184:
180:
167:
163:
162:Earth science
160:
157:
154:
151:
148:
145:
143:
140:
138:
135:
134:
133:
125:
123:
119:
115:
111:
107:
103:
99:
95:
91:
87:
82:
80:
76:
72:
69:("TSP"), the
68:
64:
60:
56:
52:
48:
41:
37:
32:
19:
2568:Local search
2514:Edmonds–Karp
2470:Bellman–Ford
2362:
2240:minimization
2072:Gauss–Newton
2022:Quasi–Newton
2007:Trust region
1915:Optimization
1832:
1810:
1792:. Springer.
1789:
1771:
1759:
1726:
1704:
1678:
1653:
1595:
1591:
1562:
1557:Das, Arnab;
1549:
1527:
1497:
1456:
1438:
1432:
1414:
1387:
1381:
1370:. Retrieved
1350:
1338:
1327:. Retrieved
1284:
1280:
1270:
1259:. Retrieved
1239:
1235:
1222:
1211:. Retrieved
1183:
1179:
1166:
1161:, p. 1.
1154:
1015:dynamic list
886:
884:
870:
860:
814:
810:
796:
782:
777:
754:
539:
537:
522:
513:
502:Please help
493:
465:
288:
253:
243:that run in
211:
176:
131:
128:Applications
83:
46:
45:
40:planar graph
2588:Tabu search
1999:Convergence
1970:Line search
1598:(3): 1061.
853:and metric
773:L-reduction
761:NP-complete
544:polynomials
280:NP-complete
276:tabu search
214:NP-complete
168:flow-rates)
2620:Categories
2419:algorithms
1927:heuristics
1919:Algorithms
1756:Aardal, K.
1468:References
1372:2022-02-17
1329:2020-09-16
1294:1801.08321
1261:2019-12-26
1213:2019-12-26
1013:This is a
719:recognized
498:to readers
209:problems.
55:finite set
2374:Paradigms
2273:quadratic
1990:Gradients
1952:Functions
1707:. Dover.
1656:. Dover.
1618:CiteSeerX
1605:0801.2193
1500:. Wiley.
1343:Cook 2016
1319:119476042
1287:: 85–97.
1242:: 11–32.
1200:207070217
920:∈
865:set cover
847:HromkoviÄŤ
799:: Equals
785:: Equals
689:∈
682:∣
635:∈
628:∣
561:∈
224:problems)
166:reservoir
137:Logistics
2605:Software
2482:Dijkstra
2313:exchange
2111:Hessians
2077:Gradient
1676:(2004).
1674:Lee, Jon
1652:(2001).
1640:14255125
1543:(eds.).
1496:(1997).
1363:Archived
1323:Archived
1252:Archived
1204:Archived
1134:See also
867:problem.
811:NPO(III)
805:Makespan
203:matching
63:discrete
2448:Kruskal
2438:BorĹŻvka
2428:Minimum
2165:General
1923:methods
1610:Bibcode
1567:Bibcode
1299:Bibcode
1069:problem
1034:Germany
861:NPO(IV)
851:MAX-SAT
797:NPO(II)
717:can be
587:bounded
494:may be
207:matroid
173:Methods
2310:Basis-
2268:Linear
2238:Convex
2082:Mirror
2039:L-BFGS
1925:, and
1840:
1817:
1796:
1734:
1711:
1686:
1660:
1638:
1620:
1577:
1504:
1445:
1421:
1394:
1317:
1198:
871:NPO(V)
783:NPO(I)
765:Turing
205:, and
92:, and
2509:Dinic
2417:Graph
1776:(PDF)
1754:. In
1752:(PDF)
1636:S2CID
1600:arXiv
1366:(PDF)
1359:(PDF)
1315:S2CID
1289:arXiv
1255:(PDF)
1236:Omega
1232:(PDF)
1207:(PDF)
1196:S2CID
1176:(PDF)
1146:Notes
1021:with
787:FPTAS
725:, and
322:graph
2475:SPFA
2443:Prim
2037:and
1838:ISBN
1815:ISBN
1794:ISBN
1732:ISBN
1709:ISBN
1684:ISBN
1658:ISBN
1575:ISBN
1502:ISBN
1443:ISBN
1419:ISBN
1392:ISBN
877:and
801:PTAS
767:and
654:and
363:and
284:P=NP
212:For
189:and
120:and
114:VLSI
2405:cut
2270:and
1628:doi
1307:doi
1285:122
1244:doi
1188:doi
1180:4OR
875:TSP
855:TSP
747:is
721:in
538:An
443:to
403:to
258:or
245:FPT
61:is
2622::
1921:,
1917::
1634:.
1626:.
1616:.
1608:.
1596:80
1594:.
1573:.
1539:;
1521:.
1492:;
1405:^
1361:.
1321:.
1313:.
1305:.
1297:.
1283:.
1279:.
1250:.
1240:54
1238:.
1234:.
1202:.
1194:.
1182:.
1178:.
757:NP
286:.
201:,
197:,
193:,
124:.
116:,
112:,
108:,
104:,
100:,
88:,
34:A
2403:/
1907:e
1900:t
1893:v
1846:.
1823:.
1802:.
1778:.
1740:.
1717:.
1692:.
1666:.
1642:.
1630::
1612::
1602::
1583:.
1569::
1547:.
1525:.
1510:.
1375:.
1345:.
1332:.
1309::
1301::
1291::
1264:.
1246::
1216:.
1190::
1184:5
1025:.
987:x
967:)
964:y
961:,
958:x
955:(
952:m
932:)
929:x
926:(
923:f
917:y
897:x
881:.
857:.
833:c
829:/
825:1
815:c
793:.
751:.
735:m
705:}
701:)
698:x
695:(
692:f
686:y
678:)
675:y
672:,
669:x
666:(
662:{
642:}
638:I
632:x
624:x
620:{
609:,
597:x
573:)
570:x
567:(
564:f
558:y
529:)
523:(
518:)
514:(
510:.
451:v
431:u
411:v
391:u
371:v
351:u
331:G
306:0
302:m
231:)
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
