29:
17:
68:
will take a long time to solve practical instances whose data are subject to slight noises and imprecisions. Smoothed complexity results are strong probabilistic results, roughly stating that, in every large enough neighbourhood of the space of inputs, most inputs are easily solvable. Thus, a low smoothed complexity means that the hardness of inputs is a "brittle" property.
1156:
75:
has been widely successful in explaining the practical performance of many algorithms, this style of analysis gives misleading results for a number of problems. Worst-case complexity measures the time it takes to solve any input, although hard-to-solve inputs might never come up in practice. In such
67:
Smoothed analysis is a hybrid of worst-case and average-case analyses that inherits advantages of both. It measures the expected performance of algorithms under slight random perturbations of worst-case inputs. If the smoothed complexity of an algorithm is low, then it is unlikely that the algorithm
102:
that is chosen over the input. The actual inputs and distribution of inputs may be different in practice from the assumptions made during the analysis: a random input may be very unlike a typical input. Because of this choice of data model, a theoretical average-case result might say little about
176:
in practice. On practical problems, the number of steps taken by the algorithm is linear in the number of variables and constraints. Yet in the theoretical worst case it takes exponentially many steps for most successfully analyzed pivot rules. This was one of the main motivations for developing
289:
1447:
is big, the adversary has more ability to increase the likelihood of hard problem instances. In this perturbation model, the expected number of iterations of the 2-opt heuristic, as well as the approximation ratios of resulting output, are bounded by polynomial functions of
689:
1163:
This bound holds for a specific pivot rule called the shadow vertex rule. The shadow vertex rule is slower than more commonly used pivot rules such as
Dantzig's rule or the steepest edge rule but it has properties that make it very well-suited to probabilistic analysis.
874:
106:
Smoothed analysis generalizes both worst-case and average-case analysis and inherits strengths of both. It is intended to be much more general than average-case complexity, while still allowing low complexity bounds to be proven.
374:
64:. It can give a more realistic analysis of the practical performance (e.g., running time, success rate, approximation quality) of the algorithm compared to analysis that uses worst-case or average-case scenarios.
187:
497:
551:
142:
for developing smoothed analysis. Spielman and Teng's JACM paper "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time" was also one of the three winners of the 2009
440:
864:
773:
596:
817:
1257:. Already in two dimensions, the 2-opt heuristic might take exponentially many iterations until finding a local optimum. In this setting, one can analyze the perturbation model where the vertices
1151:{\displaystyle C_{s}(n,d,\sigma ):=\max _{{\bar {\mathbf {A} }},{\bar {\mathbf {b} }},\mathbf {c} }~\mathbb {E} _{{\hat {\mathbf {A} }},{\hat {\mathbf {b} }}}={\rm {poly}}(d,\log n,\sigma ^{-1}).}
1393:
732:
1191:, which is the ratio between the length of the output of the algorithm and the length of the optimal solution, tends to be good in practice but can also be bad in the theoretical worst case.
1558:
to find a good partition into clusters with small pairwise distances between points in the same cluster. Lloyd's algorithm is widely used and very fast in practice, although it can take
2126:
1301:
1592:
1187:. It can take exponentially many iterations until it finds a locally optimal solution, although in practice the running time is subquadratic in the number of vertices. The
1445:
1419:
2065:
Borgwardt, Karl-Heinz; Damm, Renate; Donig, Rudolf; Joas, Gabriele (1993), "Empirical studies on the average efficiency of simplex variants under rotation symmetry",
1715:
1655:
1486:
591:
1635:
1552:
1251:
1695:
1675:
1513:
1466:
1212:
571:
76:
cases, the worst-case running time can be much worse than the observed running time in practice. For example, the worst-case complexity of solving a
2263:
98:
was first introduced to overcome the limitations of worst-case analysis. However, the resulting average-case complexity depends heavily on the
294:
2146:
2110:
1964:
284:{\displaystyle {\bar {\mathbf {A} }}\in \mathbb {R} ^{n\times d},{\bar {\mathbf {b} }}\in \mathbb {R} ^{n},\mathbf {c} \in \mathbb {R} ^{d}}
84:
is exponential, although the observed number of steps in practice is roughly linear. The simplex algorithm is in fact much faster than the
2178:
Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2007), "Worst Case and
Probabilistic Analysis of the 2-Opt Algorithm for the TSP",
115:
2268:
2051:
2028:
1987:
1845:
445:
502:
48:. Since its introduction in 2001, smoothed analysis has been used as a basis for considerable research, for problems ranging from
684:{\displaystyle \mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }}+{\hat {\mathbf {b} }}}
148:
379:
2273:
822:
743:
784:
152:
1309:
1304:
700:
37:
1173:
1594:
iterations in the worst case to find a locally optimal solution. However, assuming that the points have independent
1184:
99:
49:
1726:
2217:
1823:
1731:
45:
1736:
1595:
1260:
181:
95:
72:
1903:
Andrei, Neculai (2004), "Andrei, Neculai. "On the complexity of MINOS package for linear programming",
1944:
1561:
1828:
1767:
1188:
1424:
28:
16:
2240:
2187:
2152:
2034:
2006:
1970:
1934:
1790:
1492:
1254:
173:
53:
2001:
Dadush, Daniel; Huiberts, Sophie (2018), "A friendly smoothed analysis of the simplex method",
1398:
2142:
2106:
2045:
2024:
1981:
1960:
1841:
1811:
169:
89:
81:
1700:
1640:
1471:
576:
2232:
2197:
2134:
2098:
2092:
2074:
2016:
1952:
1883:
1833:
1782:
139:
85:
57:
1855:
1922:
1851:
1759:
1601:
1518:
1217:
144:
127:
1948:
172:
is a very efficient algorithm in practice, and it is one of the dominant algorithms for
1680:
1660:
1498:
1451:
1197:
556:
180:
For the perturbation model, we assume that the input data is perturbed by noise from a
123:
77:
2257:
2156:
1926:
1763:
131:
2038:
2244:
1794:
1657:, the expected number of iterations of the algorithm is bounded by a polynomial in
135:
1768:"Smoothed analysis: an attempt to explain the behavior of algorithms in practice"
1491:
Another local search algorithm for which smoothed analysis was successful is the
1974:
1807:
61:
2202:
2180:
Proceedings of the
Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms
2138:
2102:
1871:
2236:
2020:
1786:
1931:
Proceedings of the thirty-third annual ACM symposium on Theory of computing
1176:
algorithms have bad worst-case running times but perform well in practice.
134:
for developing smoothed analysis. The name
Smoothed Analysis was coined by
2003:
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of
Computing
1956:
1887:
2078:
369:{\displaystyle \|({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})\|_{2}\leq 1}
1837:
1555:
553:
has independent entries sampled from a
Gaussian distribution with mean
1303:
are independently sampled according to probability distributions with
21:
2192:
2011:
1939:
1180:
119:
27:
15:
2097:, Algorithms and Combinatorics, vol. 1, Springer-Verlag,
1814:(1999), "Deformed products and maximal shadows of polytopes",
492:{\displaystyle ({\bar {\mathbf {A} }},{\bar {\mathbf {b} }}).}
546:{\displaystyle ({\hat {\mathbf {A} }},{\hat {\mathbf {b} }})}
184:. For normalization purposes, we assume the unperturbed data
2133:, Cambridge: Cambridge University Press, pp. 285–308,
2173:
2171:
1874:(1987), "The Efficiency of the Simplex Method: A Survey",
435:{\displaystyle ({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})}
859:{\displaystyle T(\mathbf {A} ,\mathbf {b} ,\mathbf {c} )}
768:{\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }
691:. The smoothed input data consists of the linear program
120:
the
European Association for Theoretical Computer Science
2073:(3), Operations Research Society of America: 249–260,
866:
then the smoothed complexity of the simplex method is
812:{\displaystyle \mathbf {A} ,\mathbf {b} ,\mathbf {c} }
1703:
1683:
1663:
1643:
1604:
1564:
1521:
1501:
1474:
1454:
1427:
1401:
1312:
1263:
1220:
1200:
877:
825:
787:
746:
703:
599:
579:
559:
505:
448:
382:
297:
190:
2216:
Arthur, David; Manthey, Bodo; Röglin, Heiko (2011),
1754:
1752:
32:
A typical picture does not resemble a random bitmap.
1388:{\displaystyle f_{1},\dots ,f_{n}:^{d}\rightarrow }
1709:
1689:
1669:
1649:
1629:
1586:
1546:
1507:
1480:
1460:
1439:
1413:
1387:
1295:
1245:
1206:
1150:
858:
811:
767:
727:{\displaystyle \mathbf {c^{T}} \cdot \mathbf {x} }
726:
683:
585:
565:
545:
491:
434:
368:
283:
913:
1194:One class of problem instances can be given by
2125:Manthey, Bodo (2021), Roughgarden, Tim (ed.),
1421:, the points are uniformly distributed. When
1253:, where their pairwise distances come from a
781:If the running time of our algorithm on data
8:
2131:Beyond the Worst-Case Analysis of Algorithms
2094:The Simplex Method: A Probabilistic Analysis
351:
298:
1929:(2001), "Smoothed analysis of algorithms",
1168:Local search for combinatorial optimization
2218:"Smoothed Analysis of the k-Means Method"
2201:
2191:
2010:
1938:
1827:
1702:
1682:
1662:
1642:
1621:
1603:
1569:
1563:
1538:
1520:
1500:
1473:
1453:
1426:
1400:
1361:
1336:
1317:
1311:
1287:
1268:
1262:
1237:
1219:
1199:
1133:
1093:
1092:
1078:
1064:
1062:
1061:
1047:
1045:
1044:
1030:
1028:
1027:
1013:
1011:
1010:
988:
986:
985:
971:
969:
968:
967:
963:
962:
951:
937:
935:
934:
920:
918:
917:
916:
882:
876:
848:
840:
832:
824:
804:
796:
788:
786:
760:
752:
747:
745:
719:
709:
704:
702:
670:
668:
667:
653:
651:
650:
642:
628:
626:
625:
611:
609:
608:
600:
598:
578:
558:
529:
527:
526:
512:
510:
509:
504:
472:
470:
469:
455:
453:
452:
447:
423:
412:
411:
401:
390:
388:
387:
381:
354:
341:
330:
329:
319:
308:
306:
305:
296:
275:
271:
270:
261:
252:
248:
247:
232:
230:
229:
214:
210:
209:
194:
192:
191:
189:
1898:
1896:
1866:
1864:
1822:, American Mathematical Society: 10–19,
164:Simplex algorithm for linear programming
103:practical performance of the algorithm.
1748:
2043:
1979:
88:in practice, although the latter has
7:
24:does not resemble typical pictures.
2127:"Smoothed Analysis of Local Search"
1905:Studies in Informatics and Control
1570:
1296:{\displaystyle v_{1},\dots ,v_{n}}
1103:
1100:
1097:
1094:
14:
1079:
1065:
1048:
1031:
1014:
989:
972:
952:
938:
921:
849:
841:
833:
805:
797:
789:
761:
753:
748:
720:
710:
706:
671:
654:
643:
629:
612:
601:
530:
513:
473:
456:
391:
309:
262:
233:
195:
149:Mathematical Programming Society
138:. In 2010 Spielman received the
2264:Computational complexity theory
2091:Borgwardt, Karl-Heinz (1987),
1618:
1605:
1587:{\displaystyle e^{\Omega (n)}}
1579:
1573:
1535:
1522:
1382:
1370:
1367:
1358:
1345:
1234:
1221:
1142:
1108:
1086:
1083:
1069:
1052:
1035:
1018:
1007:
1001:
993:
976:
942:
925:
906:
888:
853:
829:
675:
658:
633:
616:
540:
534:
517:
506:
483:
477:
460:
449:
429:
417:
395:
383:
347:
335:
313:
301:
237:
199:
1:
2050:: CS1 maint: date and year (
1986:: CS1 maint: date and year (
153:American Mathematical Society
1440:{\displaystyle \theta >1}
1305:probability density function
38:theoretical computer science
1598:, each with expectation in
2290:
1185:traveling salesman problem
46:complexity of an algorithm
44:is a way of measuring the
2269:Mathematical optimization
2203:10.1007/s00453-013-9801-4
2139:10.1017/9781108637435.018
2103:10.1007/978-3-642-61578-8
2067:ORSA Journal on Computing
1933:, ACM, pp. 296–305,
1775:Communications of the ACM
1414:{\displaystyle \theta =1}
147:sponsored jointly by the
1816:Contemporary Mathematics
100:probability distribution
50:mathematical programming
2237:10.1145/2027216.2027217
2021:10.1145/3188745.3188826
1787:10.1145/1562764.1562785
1727:Average-case complexity
1710:{\displaystyle \sigma }
1650:{\displaystyle \sigma }
1637:and standard deviation
1481:{\displaystyle \theta }
586:{\displaystyle \sigma }
573:and standard deviation
92:worst-case complexity.
2274:Analysis of algorithms
1732:Pseudo-polynomial time
1711:
1691:
1671:
1651:
1631:
1596:Gaussian distributions
1588:
1548:
1509:
1482:
1462:
1441:
1415:
1389:
1297:
1247:
1208:
1152:
860:
813:
769:
728:
685:
587:
567:
547:
493:
436:
370:
285:
33:
25:
1957:10.1145/380752.380813
1888:10.1287/mnsc.33.3.301
1737:Worst-case complexity
1712:
1692:
1672:
1652:
1632:
1589:
1549:
1510:
1483:
1463:
1442:
1416:
1390:
1298:
1248:
1209:
1153:
861:
814:
770:
729:
686:
588:
568:
548:
494:
437:
371:
286:
182:Gaussian distribution
96:Average-case analysis
73:worst-case complexity
31:
20:A randomly generated
19:
2079:10.1287/ijoc.5.3.249
2005:, pp. 390–403,
1701:
1681:
1661:
1641:
1630:{\displaystyle ^{d}}
1602:
1562:
1547:{\displaystyle ^{d}}
1519:
1499:
1472:
1452:
1425:
1399:
1310:
1261:
1246:{\displaystyle ^{d}}
1218:
1198:
875:
823:
785:
744:
701:
597:
577:
557:
503:
446:
380:
295:
188:
1949:2001cs.......11050S
1189:approximation ratio
1179:One example is the
177:smoothed analysis.
2225:Journal of the ACM
1876:Management Science
1781:(10), ACM: 76–84,
1707:
1687:
1667:
1647:
1627:
1584:
1544:
1505:
1478:
1458:
1437:
1411:
1385:
1293:
1243:
1214:points in the box
1204:
1183:heuristic for the
1148:
957:
856:
809:
765:
724:
681:
583:
563:
543:
489:
432:
366:
281:
174:linear programming
54:numerical analysis
34:
26:
2148:978-1-108-49431-1
2112:978-3-540-17096-9
1966:978-1-58113-349-3
1690:{\displaystyle d}
1670:{\displaystyle n}
1508:{\displaystyle n}
1461:{\displaystyle n}
1207:{\displaystyle n}
1072:
1055:
1038:
1021:
996:
979:
960:
945:
928:
912:
678:
661:
636:
619:
566:{\displaystyle 0}
537:
520:
480:
463:
420:
398:
338:
316:
240:
202:
170:simplex algorithm
122:awarded the 2008
82:simplex algorithm
42:smoothed analysis
2281:
2248:
2247:
2222:
2213:
2207:
2206:
2205:
2195:
2175:
2166:
2165:
2164:
2163:
2122:
2116:
2115:
2088:
2082:
2081:
2062:
2056:
2055:
2049:
2041:
2014:
1998:
1992:
1991:
1985:
1977:
1942:
1923:Spielman, Daniel
1919:
1913:
1912:
1900:
1891:
1890:
1868:
1859:
1858:
1838:10.1090/conm/223
1831:
1804:
1798:
1797:
1772:
1760:Spielman, Daniel
1756:
1716:
1714:
1713:
1708:
1696:
1694:
1693:
1688:
1676:
1674:
1673:
1668:
1656:
1654:
1653:
1648:
1636:
1634:
1633:
1628:
1626:
1625:
1593:
1591:
1590:
1585:
1583:
1582:
1553:
1551:
1550:
1545:
1543:
1542:
1514:
1512:
1511:
1506:
1487:
1485:
1484:
1479:
1467:
1465:
1464:
1459:
1446:
1444:
1443:
1438:
1420:
1418:
1417:
1412:
1394:
1392:
1391:
1386:
1366:
1365:
1341:
1340:
1322:
1321:
1302:
1300:
1299:
1294:
1292:
1291:
1273:
1272:
1252:
1250:
1249:
1244:
1242:
1241:
1213:
1211:
1210:
1205:
1157:
1155:
1154:
1149:
1141:
1140:
1107:
1106:
1082:
1074:
1073:
1068:
1063:
1057:
1056:
1051:
1046:
1040:
1039:
1034:
1029:
1023:
1022:
1017:
1012:
1000:
999:
998:
997:
992:
987:
981:
980:
975:
970:
966:
958:
956:
955:
947:
946:
941:
936:
930:
929:
924:
919:
887:
886:
865:
863:
862:
857:
852:
844:
836:
818:
816:
815:
810:
808:
800:
792:
774:
772:
771:
766:
764:
756:
751:
733:
731:
730:
725:
723:
715:
714:
713:
690:
688:
687:
682:
680:
679:
674:
669:
663:
662:
657:
652:
646:
638:
637:
632:
627:
621:
620:
615:
610:
604:
592:
590:
589:
584:
572:
570:
569:
564:
552:
550:
549:
544:
539:
538:
533:
528:
522:
521:
516:
511:
498:
496:
495:
490:
482:
481:
476:
471:
465:
464:
459:
454:
441:
439:
438:
433:
428:
427:
422:
421:
413:
406:
405:
400:
399:
394:
389:
375:
373:
372:
367:
359:
358:
346:
345:
340:
339:
331:
324:
323:
318:
317:
312:
307:
290:
288:
287:
282:
280:
279:
274:
265:
257:
256:
251:
242:
241:
236:
231:
225:
224:
213:
204:
203:
198:
193:
140:Nevanlinna Prize
86:ellipsoid method
58:machine learning
2289:
2288:
2284:
2283:
2282:
2280:
2279:
2278:
2254:
2253:
2252:
2251:
2220:
2215:
2214:
2210:
2177:
2176:
2169:
2161:
2159:
2149:
2124:
2123:
2119:
2113:
2090:
2089:
2085:
2064:
2063:
2059:
2042:
2031:
2000:
1999:
1995:
1978:
1967:
1927:Teng, Shang-Hua
1921:
1920:
1916:
1902:
1901:
1894:
1870:
1869:
1862:
1848:
1812:Ziegler, Günter
1806:
1805:
1801:
1770:
1764:Teng, Shang-Hua
1758:
1757:
1750:
1745:
1723:
1699:
1698:
1679:
1678:
1659:
1658:
1639:
1638:
1617:
1600:
1599:
1565:
1560:
1559:
1534:
1517:
1516:
1497:
1496:
1470:
1469:
1450:
1449:
1423:
1422:
1397:
1396:
1357:
1332:
1313:
1308:
1307:
1283:
1264:
1259:
1258:
1233:
1216:
1215:
1196:
1195:
1170:
1129:
961:
878:
873:
872:
821:
820:
783:
782:
742:
741:
705:
699:
698:
595:
594:
575:
574:
555:
554:
501:
500:
444:
443:
410:
386:
378:
377:
350:
328:
304:
293:
292:
269:
246:
208:
186:
185:
166:
161:
151:(MPS) and the
145:Fulkerson Prize
128:Daniel Spielman
113:
90:polynomial-time
12:
11:
5:
2287:
2285:
2277:
2276:
2271:
2266:
2256:
2255:
2250:
2249:
2208:
2167:
2147:
2117:
2111:
2083:
2057:
2029:
1993:
1965:
1914:
1892:
1882:(3): 301–334,
1860:
1846:
1829:10.1.1.80.3241
1799:
1747:
1746:
1744:
1741:
1740:
1739:
1734:
1729:
1722:
1719:
1706:
1686:
1666:
1646:
1624:
1620:
1616:
1613:
1610:
1607:
1581:
1578:
1575:
1572:
1568:
1541:
1537:
1533:
1530:
1527:
1524:
1504:
1493:k-means method
1477:
1457:
1436:
1433:
1430:
1410:
1407:
1404:
1384:
1381:
1378:
1375:
1372:
1369:
1364:
1360:
1356:
1353:
1350:
1347:
1344:
1339:
1335:
1331:
1328:
1325:
1320:
1316:
1290:
1286:
1282:
1279:
1276:
1271:
1267:
1240:
1236:
1232:
1229:
1226:
1223:
1203:
1169:
1166:
1161:
1160:
1159:
1158:
1147:
1144:
1139:
1136:
1132:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1105:
1102:
1099:
1096:
1091:
1088:
1085:
1081:
1077:
1071:
1067:
1060:
1054:
1050:
1043:
1037:
1033:
1026:
1020:
1016:
1009:
1006:
1003:
995:
991:
984:
978:
974:
965:
954:
950:
944:
940:
933:
927:
923:
915:
911:
908:
905:
902:
899:
896:
893:
890:
885:
881:
855:
851:
847:
843:
839:
835:
831:
828:
807:
803:
799:
795:
791:
779:
778:
777:
776:
763:
759:
755:
750:
736:
735:
734:
722:
718:
712:
708:
677:
673:
666:
660:
656:
649:
645:
641:
635:
631:
624:
618:
614:
607:
603:
582:
562:
542:
536:
532:
525:
519:
515:
508:
488:
485:
479:
475:
468:
462:
458:
451:
442:of the matrix
431:
426:
419:
416:
409:
404:
397:
393:
385:
365:
362:
357:
353:
349:
344:
337:
334:
327:
322:
315:
311:
303:
300:
278:
273:
268:
264:
260:
255:
250:
245:
239:
235:
228:
223:
220:
217:
212:
207:
201:
197:
165:
162:
160:
157:
112:
109:
78:linear program
13:
10:
9:
6:
4:
3:
2:
2286:
2275:
2272:
2270:
2267:
2265:
2262:
2261:
2259:
2246:
2242:
2238:
2234:
2230:
2226:
2219:
2212:
2209:
2204:
2199:
2194:
2189:
2185:
2181:
2174:
2172:
2168:
2158:
2154:
2150:
2144:
2140:
2136:
2132:
2128:
2121:
2118:
2114:
2108:
2104:
2100:
2096:
2095:
2087:
2084:
2080:
2076:
2072:
2068:
2061:
2058:
2053:
2047:
2040:
2036:
2032:
2030:9781450355599
2026:
2022:
2018:
2013:
2008:
2004:
1997:
1994:
1989:
1983:
1976:
1972:
1968:
1962:
1958:
1954:
1950:
1946:
1941:
1936:
1932:
1928:
1924:
1918:
1915:
1910:
1906:
1899:
1897:
1893:
1889:
1885:
1881:
1877:
1873:
1867:
1865:
1861:
1857:
1853:
1849:
1847:9780821806746
1843:
1839:
1835:
1830:
1825:
1821:
1817:
1813:
1809:
1803:
1800:
1796:
1792:
1788:
1784:
1780:
1776:
1769:
1765:
1761:
1755:
1753:
1749:
1742:
1738:
1735:
1733:
1730:
1728:
1725:
1724:
1720:
1718:
1704:
1684:
1664:
1644:
1622:
1614:
1611:
1608:
1597:
1576:
1566:
1557:
1539:
1531:
1528:
1525:
1502:
1494:
1489:
1475:
1455:
1434:
1431:
1428:
1408:
1405:
1402:
1379:
1376:
1373:
1362:
1354:
1351:
1348:
1342:
1337:
1333:
1329:
1326:
1323:
1318:
1314:
1306:
1288:
1284:
1280:
1277:
1274:
1269:
1265:
1256:
1238:
1230:
1227:
1224:
1201:
1192:
1190:
1186:
1182:
1177:
1175:
1167:
1165:
1145:
1137:
1134:
1130:
1126:
1123:
1120:
1117:
1114:
1111:
1089:
1075:
1058:
1041:
1024:
1004:
982:
948:
931:
909:
903:
900:
897:
894:
891:
883:
879:
871:
870:
869:
868:
867:
845:
837:
826:
801:
793:
757:
740:
739:
737:
716:
697:
696:
694:
693:
692:
664:
647:
639:
622:
605:
580:
560:
523:
486:
466:
424:
414:
407:
402:
376:for all rows
363:
360:
355:
342:
332:
325:
320:
276:
266:
258:
253:
243:
226:
221:
218:
215:
205:
183:
178:
175:
171:
163:
158:
156:
154:
150:
146:
141:
137:
133:
132:Shanghua Teng
129:
125:
121:
117:
110:
108:
104:
101:
97:
93:
91:
87:
83:
79:
74:
69:
65:
63:
59:
55:
51:
47:
43:
39:
30:
23:
18:
2228:
2224:
2211:
2183:
2179:
2160:, retrieved
2130:
2120:
2093:
2086:
2070:
2066:
2060:
2002:
1996:
1930:
1917:
1908:
1904:
1879:
1875:
1819:
1815:
1808:Amenta, Nina
1802:
1778:
1774:
1490:
1193:
1178:
1174:local search
1172:A number of
1171:
1162:
819:is given by
780:
179:
167:
136:Alan Edelman
114:
105:
94:
70:
66:
41:
35:
2231:(5): 1–31,
2186:: 190–264,
1872:Shamir, Ron
738:subject to
124:Gödel Prize
62:data mining
2258:Categories
2193:2302.06889
2162:2022-06-15
2012:1711.05667
1940:cs/0111050
1911:(1): 35–46
1743:References
1515:points in
499:The noise
291:satisfies
80:using the
2157:221680879
1824:CiteSeerX
1705:σ
1645:σ
1571:Ω
1476:θ
1429:θ
1403:θ
1380:θ
1368:→
1327:…
1278:…
1135:−
1131:σ
1121:
1070:^
1053:¯
1036:^
1019:¯
994:^
977:^
943:¯
926:¯
904:σ
758:≤
717:⋅
695:maximize
676:^
659:¯
634:^
617:¯
593:. We set
581:σ
535:^
518:^
478:¯
461:¯
418:¯
396:¯
361:≤
352:‖
336:¯
314:¯
299:‖
267:∈
244:∈
238:¯
219:×
206:∈
200:¯
71:Although
2046:citation
2039:11868079
1982:citation
1766:(2009),
1721:See also
1554:, it is
1495:. Given
159:Examples
2245:5253105
1945:Bibcode
1856:1661377
1795:7904807
1556:NP-hard
155:(AMS).
111:History
2243:
2155:
2145:
2109:
2037:
2027:
1973:
1963:
1854:
1844:
1826:
1793:
1395:. For
959:
60:, and
22:bitmap
2241:S2CID
2221:(PDF)
2188:arXiv
2153:S2CID
2035:S2CID
2007:arXiv
1971:S2CID
1935:arXiv
1791:S2CID
1771:(PDF)
1181:2-opt
2143:ISBN
2107:ISBN
2052:link
2025:ISBN
1988:link
1975:1471
1961:ISBN
1842:ISBN
1697:and
1468:and
1432:>
1255:norm
168:The
130:and
118:and
2233:doi
2198:doi
2135:doi
2099:doi
2075:doi
2017:doi
1953:doi
1884:doi
1834:doi
1820:223
1783:doi
1118:log
914:max
126:to
116:ACM
36:In
2260::
2239:,
2229:58
2227:,
2223:,
2196:,
2184:68
2182:,
2170:^
2151:,
2141:,
2129:,
2105:,
2069:,
2048:}}
2044:{{
2033:,
2023:,
2015:,
1984:}}
1980:{{
1969:,
1959:,
1951:,
1943:,
1925:;
1909:13
1907:,
1895:^
1880:33
1878:,
1863:^
1852:MR
1850:,
1840:,
1832:,
1818:,
1810:;
1789:,
1779:52
1777:,
1773:,
1762:;
1751:^
1717:.
1677:,
1488:.
910::=
56:,
52:,
40:,
2235::
2200::
2190::
2137::
2101::
2077::
2071:5
2054:)
2019::
2009::
1990:)
1955::
1947::
1937::
1886::
1836::
1785::
1685:d
1665:n
1623:d
1619:]
1615:1
1612:,
1609:0
1606:[
1580:)
1577:n
1574:(
1567:e
1540:d
1536:]
1532:1
1529:,
1526:0
1523:[
1503:n
1456:n
1435:1
1409:1
1406:=
1383:]
1377:,
1374:0
1371:[
1363:d
1359:]
1355:1
1352:,
1349:0
1346:[
1343::
1338:n
1334:f
1330:,
1324:,
1319:1
1315:f
1289:n
1285:v
1281:,
1275:,
1270:1
1266:v
1239:d
1235:]
1231:1
1228:,
1225:0
1222:[
1202:n
1146:.
1143:)
1138:1
1127:,
1124:n
1115:,
1112:d
1109:(
1104:y
1101:l
1098:o
1095:p
1090:=
1087:]
1084:)
1080:c
1076:,
1066:b
1059:+
1049:b
1042:,
1032:A
1025:+
1015:A
1008:(
1005:T
1002:[
990:b
983:,
973:A
964:E
953:c
949:,
939:b
932:,
922:A
907:)
901:,
898:d
895:,
892:n
889:(
884:s
880:C
854:)
850:c
846:,
842:b
838:,
834:A
830:(
827:T
806:c
802:,
798:b
794:,
790:A
775:.
762:b
754:x
749:A
721:x
711:T
707:c
672:b
665:+
655:b
648:=
644:b
640:,
630:A
623:+
613:A
606:=
602:A
561:0
541:)
531:b
524:,
514:A
507:(
487:.
484:)
474:b
467:,
457:A
450:(
430:)
425:i
415:b
408:,
403:i
392:a
384:(
364:1
356:2
348:)
343:i
333:b
326:,
321:i
310:a
302:(
277:d
272:R
263:c
259:,
254:n
249:R
234:b
227:,
222:d
216:n
211:R
196:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
