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